[cpp] #include <iostream> #include <cstdio> #include <cstring> #define INF 0x7ffffff//如果設為0x7fffffff在執行算法時溢出。 #define maxn 100 using namespace std; int n; int edge[maxn][maxn]; int a[maxn][maxn], path[maxn][maxn]; void floyd() { int i, j, k; for( i = 0; i < n; i++ ) { for( j = 0; j < n; j++) { a[i][j] = edge[i][j]; if( i != j && a[i][j] < INF ) { path[i][j] = i; } else { path[i][j] = -1; } } } for( k = 0; k < n; k++ ) { for( i = 0; i < n; i++ ) { for( j = 0; j < n; j++ ) { if( k == i || k == j ) { continue; } if( a[i][k] + a[k][j] < a[i][j] ) { a[i][j] = a[i][k] + a[k][j]; path[i][j] = path[k][j]; } } } } } void output() { int i, j; int shortest[maxn]; for( i = 0; i < n; i++ ) { for( j = 0; j < n; j++ ) { if( i == j) { continue; } printf( "%d->%d\t%d\t", i, j, a[i][j] ); memset( shortest, 0, sizeof(shortest) ); int k = 0; shortest[k] = j; while( path[i][shortest[k]] != i) { k++; shortest[k] = path[i][shortest[k-1]]; } k++; shortest[k] = i; for( int t = k; t >0; t-- ) { printf( "%d->", shortest[t] ); } printf( "%d\n",shortest[0] ); } } return; } void init() { int i, j; int u, v, w; scanf("%d", &n); for( i = 0; i < n; i++ ) { for( j = 0; j < n; j++ ) { if(i != j) { edge[i][j] = INF; } else { edge[i][j] = 0; } } } while( 1 ) { scanf("%d%d%d", &u, &v, &w); if( u == -1 && v == -1 && w == -1 ) { break; } edge[u][v] = w; } } int main() { init(); floyd(); output(); return 0; } /************************** 測試數據： 4 0 1 1 0 3 4 1 2 9 1 3 2 2 0 3 2 1 5 2 3 8 3 2 6 -1 -1 -1 ***********************/
