1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<queue> 6 #include<vector> 7 #include<cstring> 8 #include<cmath> 9 using namespace std;10 #define N 11111 int f[N][N],lj[N][N];12 int n,m;13 vector<int>q;14 void init()15 {16     memset(f,0,sizeof(0));17     memset(lj,-1,sizeof(lj));18 }19 void floyd()20 {21     for(int k=1;k<=n;k++)22     {23         for(int i=1;i<=n;i++)24         {25             for(int j=1;j<=n;j++)26             {27                 if(f[i][j]>f[i][k]+f[k][j])28                 {29                     f[i][j]=f[i][k]+f[k][j];30                     lj[i][j]=k;31                 }32             }33         }34     }35 }36 37 void dfs(int u,int v)38 {39     if(lj[u][v]==-1)return ;40     dfs(u,lj[u][v]);41     q.push_back(lj[u][v]);42     dfs(lj[u][v],v);43 }44 void print()45 {46     for(int i=1;i<=n;i++)47     {48         for(int j=1;j<=n;j++)49         {50             if(i==j)continue;51             printf("%d->%d   =   %d     ",i,j,f[i][j]);52             q.clear();53             q.push_back(i);54             dfs(i,j);55             q.push_back(j);56             for(int k=0;k<q.size();k++)printf("%d ",q[k]);57             printf("\n");58         }59     }60 }61 int main()62 {63     while(scanf("%d%d",&n,&m)!=EOF)64     {65         init();66         for(int i=1;i<=n;i++)67         {68             for(int j=1;j<=n;j++)scanf("%d",&f[i][j]);69         }70         floyd();71         print();72     }73     return 0;74 }