4#include<iostream.h>
const vtxnum=64;   //圖的最大頂點(diǎn)數(shù) 
struct graphtp{
          int  vernum;                 //景點(diǎn)個(gè)數(shù)
	      char vexs[vtxnum];           //景點(diǎn)名稱(字母)
		  int  arcs[vtxnum][vtxnum];   //景點(diǎn)間路徑信息的鄰接矩陣
};
struct pathtp{                         //(棧)路徑類型
          char data[vtxnum][vtxnum][vtxnum];//路徑
          int top[vtxnum][vtxnum];          //
};
void create(graphtp &image)
{
	 cout<<"please input the number of 景點(diǎn)\n";
	 cin>>image.vernum;                  //讀入景點(diǎn)個(gè)數(shù)
	 cout<<"please input the name of the "<<image.vernum<<" 景點(diǎn)(用一個(gè)字母表示)\n"; //輸入景點(diǎn)名稱(字母)
     for(int k=1;k<=image.vernum;k++)
		 cin>>image.vexs[k];           
	 for(int i=1;i<=image.vernum;i++)                //初始化鄰接矩陣
		 for(int j=1;j<=image.vernum;j++)
			 image.arcs[i][j]=0;
	 cout<<"please input the adjacent matrix\n"      //輸入鄰接矩陣
		 <<"if there were no path between two vertexes  then input number\"100\"\n"
		 <<"                                            else input the reality number\n";
		 for(int h=1;h<=image.vernum;h++)
			 for(int l=1;l<=image.vernum;l++)
				 cin>>image.arcs[h][l];

}
void floyd(graphtp image,int distance[vtxnum][vtxnum],pathtp &path) // 用弗洛伊德計(jì)算最短路經(jīng)
{
     for(int i=1;i<=image.vernum;i++)
		 for(int j=1;j<=image.vernum;j++)
		 {
			 distance[i][j]=image.arcs[i][j];     //把原始鄰接矩陣存入初始路徑長(zhǎng)度  
			 if(distance[i][j]<=100)              //當(dāng)路徑長(zhǎng)度小于MAX時(shí)，將此路徑儲(chǔ)存
			 {
				 path.data[i][j][1]=image.vexs[i];
				 path.data[i][j][2]=image.vexs[j];
				 path.top[i][j]=2;
			 }
		 }
     for(int k=1;k<=image.vernum;k++)
		 for(int i=1;i<=image.vernum;i++)
		     for(int j=1;j<=image.vernum;j++)
			 {
				 if((distance[i][k]+distance[k][j])<distance[i][j]) //當(dāng)i經(jīng)k到j(luò)的路徑長(zhǎng)度小于i到j(luò)的直接路徑長(zhǎng)度
				 {                                                  //修改路徑長(zhǎng)度并修改路徑
					 distance[i][j]=distance[i][k]+distance[k][j];
                     for(int p=path.top[i][j];p>=(path.top[i][j]-1);p--)  //用棧儲(chǔ)存路徑
						 path.data[i][j][p+1]=path.data[i][j][p];
					 path.data[i][j][path.top[i][j]]=image.vexs[k];
				     path.top[i][j]++;
				 }
			 }
}
void write(graphtp image)  //用一般方法輸出圖的信息，以檢驗(yàn)鄰接矩陣的圖的建立是否成功
{
	 
	cout<<"the 景點(diǎn) are\n";
	 for(int i=1;i<=image.vernum;i++)
		 cout<<image.vexs[i]<<"  ";
	 cout<<endl;
	 cout<<"the adjacent matrix of the graph 景點(diǎn) is\n";
	 for(int h=1;h<=image.vernum;h++)
			 for(int l=1;l<=image.vernum;l++)
			 {
				 cout<<image.arcs[h][l]<<"  ";
			     if (l==image.vernum)  cout<<endl;
			 }
	 cout<<endl;
}
void write_floyd(graphtp image,int distance[vtxnum][vtxnum],pathtp &path)
{    //輸出圖的最短路徑及其長(zhǎng)度
    int c=1;   //用“c”來(lái)表示第c個(gè)路徑
	for(int i=1;i<=image.vernum;i++)
		     for(int j=1;j<=image.vernum;j++)
			    if ((distance[i][j]<100)&&distance[i][j]>0) //當(dāng)路徑長(zhǎng)度小于MAX、大于0時(shí)，輸出此路徑
				{
			        cout<<"the "<<c<<" shortest path is\n";
			    	for(int p=1;p<=path.top[i][j];p++)
					     cout<<path.data[i][j][p]<<" ";
			    	c++;
			    	cout<<endl;
				    cout<<"and the length of the path is "<<distance[i][j]<<endl;//輸出此路徑的長(zhǎng)度
			    	cout<<endl;
				}
}
void main()
{
     graphtp graph;
	 pathtp path;
	 int length[vtxnum][vtxnum];
	 create(graph);
	 write(graph);
	 floyd(graph,length,path);
	 write_floyd(graph,length,path);
}