- #include <iostream>
- #include <string.h>
- using namespace std;
-
-
- #define N 200
-
- int path[N][N]; //記錄路徑
- int s[N][N]; //記錄兩點間的最短距離
- int n,table[N][N];
-
- void Floyd()
- {
- int i,j,k;
- for(i=0;i<n;i++)
- for(j=0;j<n;j++)
- {
- s[i][j] = table[i][j];
- path[i][j] = j;
- }
- for(k=0;k<n;k++)
- for(i=0;i<n;i++)
- for(j=0;j<n;j++)
- if(s[i][j] > s[i][k] + s[k][j])
- {
- s[i][j] = s[i][k] + s[k][j];
- path[i][j] = path[i][k];
- }
- }
- void output(int st , int end)
- {
- int next;
- printf("%d",st);
- next = path[st][end];
- do{
- printf("->%d",next);
- next = path[next][end];
- }while(next != end);
- }
-
- int main()
- {
- while(scanf("%d",&n))
- {
- for(int i=0;i<n;i++)
- for(int j=0;j<n;j++)
- cin>>table[i][j];
- Floyd();
- output(n-1,0);
- }
- }
|
