// 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_DIJ(Graph G,bool** path)
{
	int *D;
	D=(int*)malloc(G.vexnum*sizeof(int));
	bool *final;
	final=(bool*)malloc(G.vexnum*sizeof(bool));
	memset(final,0,G.vexnum*sizeof(bool));

	for(int i=0;i<G.vexnum;i++)
	{
		D[i]=INT_MAX;
		if(G.am[0][i].adj<INT_MAX)
		{
			D[i]=G.am[0][i].adj;
		}
		path[i][i]=true;						//terminal point
		path[i][0]=true;						//starting point
	}
	final[0]=true;

	for(int i=1;i<G.vexnum;i++)
	{
		int min=INT_MAX;
		int min_indx=-1;
		for(int j=0;j<G.vexnum;j++)
		{
			if(final[j]==false)
			{
				if(D[j]<min)
				{
					min=D[j];
					min_indx=j;
				}
			}
		}
		final[min_indx]=true;
		
		if(min_indx!=-1)
		{
			for(int j=1;j<G.vexnum;j++)
			{
				if(final[j]==false)
				{
					if(D[j]>D[min_indx]+G.am[min_indx][j].adj)
					{
						D[j]=D[min_indx]+G.am[min_indx][j].adj;

						for(int k=0;k<G.vexnum;k++)
						{
							path[j][k]=path[min_indx][k];
						}
						path[j][j]=true;
					}
				}
			}
		}
	}

	cout<<"The shortest path from v0 to "<<endl;
	for(int j=0;j<G.vexnum;j++)
	{
		cout<<"v"<<j<<":"<<D[j]<<endl;
		for(int i=0;i<G.vexnum;i++)
		{
			cout<<path[j][i]<<" ";
		}
		cout<<endl;
	}
}

int main(void)
{
	Graph G;
	InitGraph(G);
	
	bool **path;
	path=(bool**)malloc(G.vexnum*sizeof(bool*));
	for(int i=0;i<G.vexnum;i++)
	{
		path[i]=(bool*)malloc(G.vexnum*sizeof(bool));
		memset(path[i],false,G.vexnum*sizeof(bool));
	}

	ShortestPath_DIJ(G,path);

	system("pause");
	return 0;
}