// exam1.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <stack>
using namespace std;

#define MAXVEX 20
#define INT_MAX 10000

typedef struct ArcNode
{
	int adj;
	void* info;
}ArcNode;

typedef ArcNode AdjMat[MAXVEX][MAXVEX];

typedef struct
{
	int vexnum;
	int arcnum;
	AdjMat am;
}Graph;

void InitGraph(Graph& G)
{
	cout<<"Please enter the number of vertex:"<<endl;
	cin>>G.vexnum;
	cout<<"Please enter the Arc of the graph:"<<endl;
	cout<<"head tail weight"<<endl;

	for(int i=0;i<G.vexnum;i++)
	{
		for(int j=0;j<G.vexnum;j++)
		{
			if(i==j)
			{
				G.am[i][j].adj=0;
			}
			else
			{
				G.am[i][j].adj=INT_MAX;
			}
		}
	}

	int vex1,vex2,w;
	while(cin>>vex1>>vex2>>w)
	{
		G.am[vex1][vex2].adj=w;
	}
}


void ShortestPath_FLOYD(Graph G,bool*** &path,int** &D)
{
	path=(bool***)malloc(G.vexnum*sizeof(bool**));
	for(int i=0;i<G.vexnum;i++)
	{
		path[i]=(bool**)malloc(sizeof(bool*)*G.vexnum);
	}
	for(int i=0;i<G.vexnum;i++)
	{
		for(int j=0;j<G.vexnum;j++)
		{
			path[i][j]=(bool*)malloc(G.vexnum*sizeof(bool));
		}
	}

	D=(int**)malloc(G.vexnum*sizeof(int*));
	for(int i=0;i<G.vexnum;i++)
	{
		D[i]=(int*)malloc(G.vexnum*sizeof(int));
	}

	for(int i=0;i<G.vexnum;i++)
	{
		for(int j=0;j<G.vexnum;j++)
		{
			D[i][j]=INT_MAX;
			for(int k=0;k<G.vexnum;k++)
			{
				path[i][j][k]=false;
			}
			if(G.am[i][j].adj<INT_MAX)
			{
				D[i][j]=G.am[i][j].adj;
				path[i][j][i]=true;
				path[i][j][j]=true;
			}
		}
	}

	for(int k=0;k<G.vexnum;k++)
	{
		for(int i=0;i<G.vexnum;i++)
		{
			for(int j=0;j<G.vexnum;j++)
			{
				if(D[i][k]+D[k][j]<D[i][j])
				{
					D[i][j]=D[i][k]+D[k][j];

					for(int m=0;m<G.vexnum;m++)
					{
						path[i][j][m]=path[i][k][m] || path[k][j][m];
					}
				}
			}
		}
	}
}

void show_result(Graph G,bool***path,int**D)
{
	cout<<"The distance matrix is:"<<endl;
	for(int i=0;i<G.vexnum;i++)
	{
		for(int j=0;j<G.vexnum;j++)
		{
			cout<<D[i][j]<<" ";
		}
		cout<<endl;
	}

	cout<<"The path among nodes arw"<<endl;

	for(int i=0;i<G.vexnum;i++)
	{
		for(int j=0;j<G.vexnum;j++)
		{
			cout<<"The path between v"<<i<<" and v"<<j<<" is:"<<endl;
			for(int k=0;k<G.vexnum;k++)
			{
				cout<<path[i][j][k]<<" ";
			}
			cout<<endl<<"------------------------------------------------"<<endl;
		}
	}
}

int main(void)
{
	Graph G;
	InitGraph(G);
	
	bool ***path;
	int **D;
	ShortestPath_FLOYD(G,path,D);

	show_result(G,path,D);

	system("pause");
	return 0;
}