#include<iostream>
using namespace std;

#define INFINITY 1000
#define MAX_VERTEX_NUM  20
#define True 1
#define FALSE 0

struct MGraph{
	char vexs[MAX_VERTEX_NUM];
     int  arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
	  int vexnum,arcnum;
};

int LocateVex(MGraph &G, char ch){ 
	 int i,k;
	 for(i=0;i<G.vexnum;++i)
	 {
	   if(ch==G.vexs[i])
		 k=i;
	 }
  return k;
 }

void CreateGraph(MGraph &G){
	int i,j,k,w;
    char v1,v2;
	cout<<"請輸入該圖的結點數和弧數:";
	cin>>G.vexnum>>G.arcnum;
	cout<<"請輸入圖的頂點向量:";
	for(i=0;i<G.vexnum;i++)
		cin>>G.vexs[i];
	for(i=0;i<G.vexnum;i++){
		for(j=0;j<G.vexnum;j++)
			G.arcs[i][j] =INFINITY;
		G.arcs[i][i]=0;
	}
	for(k=0;k<G.arcnum;k++){
			cout<<"請輸入一條邊依附的頂點及權值"<<endl;
			cin>>v1>>v2>>w;
			i=LocateVex(G,v1);	j=LocateVex(G,v2);
			G.arcs[i][j]=w;
			G.arcs[j][i]=G.arcs[i][j];
	}
	cout<<"--------初始鄰接矩陣---------"<<endl;
	for(i=0;i<G.vexnum;i++){
		 for(j=0;j<G.vexnum;j++)
			 cout<<G.arcs[i][j]<<"   ";
		 cout<<endl;
	 }
}

//void ShortestPath_FLOYD(MGraph G,char P[20][20][20],int D[20][20])
void ShortestPath_FLOYD(MGraph G,int D[20][20])
{ 
	int a[20];
	int v,u,w;
	for(v=0;v<G.vexnum;v++)//-------D(-1)-------
	{
	   for(w=0;w<G.vexnum;w++)
	   {
		  D[v][w]=G.arcs[v][w];
	    /* for (u=0;u<G.vexnum;u++)
		     P[v][w][u]=NULL;
	     if (D[v][w]!=20000)
		 {
		    P[v][w][v]=True;
			P[v][w][w]=True;
		 }*/
	   }
	}	
	for(u=0;u<G.vexnum;u++)
	{
		for(v=0;v<G.vexnum;v++)
		{
			for(w=0;w<G.vexnum;w++)
			{
				if (D[v][u]+D[u][w]<D[v][w])
					D[v][w]=D[v][u]+D[u][w];
				/*for(i=0;i<G.vexnum;i++)
				{
					P[v][w][i]=P[v][u][i]||P[u][w][i];
				}*/
			}
		}
	}
	cout<<"-------頂點間最短路徑矩陣--------"<<endl;
  for(v=0;v<G.vexnum;v++)
	 {
		 for(w=0;w<G.vexnum;++w)
			 cout<<D[v][w]<<" ";
		 cout<<endl;
	 }
/*for(v=0;v<G.vexnum;v++)
	{
		for(u=0;u<G.vexnum;u++)
		{
			for(w=0;w<G.vexnum;w++)
			{ 
               cout<<P[v][u][w]<<" ";
			}
		   cout<<endl;
		}
	}*/
  for(v=0;v<G.vexnum;v++)
  {   
	  int count1=1;
	  a[v]=0;
	  for(w=0;w<G.vexnum;w++)
	  {
		  if(a[v]<D[v][w]&&D[v][w]<INFINITY){
			  a[v]=D[v][w];
			  //++count1;
			  count1=w+1;
		  }
	  }
	  cout<<"若選擇第"<<v+1<<"個村莊建醫院,與它距離最遠的村莊是第"<<count1<<"個村莊,路程是"<<a[v]<<endl;
  }
  int min=a[0];
  int count2=0;
  for(v=0;v<G.vexnum;v++)
  { 
	  if(min>=a[v]){
         min=a[v];
		 ++count2;
	  }
  }
  cout<<"在第"<<count2<<"個村莊建醫院可使離醫院最遠的村莊到醫院的路程最短"<<endl;
  cout<<"其最短路徑是:"<<min<<endl;

}

void main (){ 
	MGraph G;
    CreateGraph(G);
	int D[20][20];
	ShortestPath_FLOYD(G,D);
}