1 /*每对顶点之间最短路径Floyd 2011.8.27*/

  2

  3 #include <iostream>

  4 #include <stack>

  5 #define M 100

  6 #define N 100

  7 using namespace std;

  8

  9 typedef struct node

 10 {

 11     int matrix[N][M];      //邻接矩阵

 12     int n;                 //顶点数

 13     int e;                 //边数

 14 }MGraph;

 15

 16 void FloydPath(MGraph g,int dist[N][M],int path[N][M])

 17 {

 18     int i,j,k;

 19     for(i=0;i<g.n;i++)

 20         for(j=0;j<g.n;j++)

 21         {

 22             if(g.matrix[i][j]>0)

 23             {

 24                 dist[i][j]=g.matrix[i][j];

 25                 path[i][j]=i;

 26             }

 27             else

 28             {

 29                 if(i!=j)

 30                 {

 31                     dist[i][j]=INT_MAX;

 32                     path[i][j]=-1;

 33                 }

 34                 else

 35                 {

 36                     dist[i][j]=0;

 37                     path[i][j]=i;

 38                 }

 39             }

 40         }

 41     for(k=0;k<g.n;k++)     //中间插入点(注意理解k为什么只能在最外层)

 42         for(i=0;i<g.n;i++)

 43             for(j=0;j<g.n;j++)

 44             {

 45                 if((dist[i][k]>0&&dist[i][k]<INT_MAX)&&      //防止加法溢出

 46                       (dist[k][j]>0&&dist[k][j]<INT_MAX)&&

 47                     dist[i][k]+dist[k][j]<dist[i][j])

 48                 {

 49                     dist[i][j]=dist[i][k]+dist[k][j];

 50                     path[i][j]=path[k][j];   //path[i][j]记录从i到j的最短路径上j的前一个顶点

 51                    }

 52             }

 53 }

 54

 55 void showPath(int path[N][M],int s,int t)    //打印出最短路径

 56 {

 57     stack<int> st;

 58     int v=t;

 59     while(t!=s)

 60     {

 61         st.push(t);

 62         t=path[s][t];

 63     }

 64     st.push(t);

 65     while(!st.empty())

 66     {

 67         cout<<st.top()<<" ";

 68         st.pop();

 69     }

 70

 71 }

 72

 73 int main(int argc, char *argv[])

 74 {

 75     int e,n;

 76     while(cin>>e>>n&&e!=0)

 77     {

 78         int i,j;

 79         int s,t,w;

 80         MGraph g;

 81         int dist[N][M],path[N][M];

 82         g.n=n;

 83         g.e=e;

 84         for(i=0;i<g.n;i++)

 85             for(j=0;j<g.n;j++)

 86                 g.matrix[i][j]=0;

 87         for(i=0;i<e;i++)

 88         {

 89             cin>>s>>t>>w;

 90             g.matrix[s][t]=w;

 91         }

 92         FloydPath(g,dist,path);

 93         for(i=0;i<g.n;i++)

 94             for(j=0;j<g.n;j++)

 95                 {

 96                     if(dist[i][j]>0&&dist[i][j]<INT_MAX)

 97                     {

 98                         showPath(path,i,j);

 99                         cout<<dist[i][j]<<endl;

100                     }

101                 }

102     }

103     return 0;

104 }