Floydアルゴリズム+パスレコード

11322 ワード

#include
#include
using namespace std;
const int maxn = 100;
const int inf = 0x3f3f3f3f;
int cost[maxn][maxn];
int lowcost[maxn][maxn];
int path[maxn][maxn];
void floyd(int n){
    memcpy(lowcost,cost,sizeof(cost));
    memset(path,-1,sizeof(path));
    for(int k = 1;k <= n;k++){          //floyd   k     
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                if(lowcost[i][j] > lowcost[i][k] + lowcost[k][j]){
                    lowcost[i][j] = lowcost[i][k] + lowcost[k][j];
                    path[i][j] = k;     //    
                }
            }
        }
    }
}
void disp(int u,int v){     //   u  v    
    if(path[u][v] == -1)    return;     //    -1           -1    (  u v       )
    // u v    path[u][v]  (   u path[u][v]       path[u][v]        path[u][v] v)
    disp(u,path[u][v]);
    cout << "-->" << path[u][v];
    disp(path[u][v],v);
}
int n,m;        //       
int u,v,w;      // u v    w
int main()
{
    cin >> n >> m;
    memset(cost,inf,sizeof(cost));  //               
    while(m--){
        cin >> u >> v >> w;
        cost[u][v] = cost[v][u] = w;    
    }
    floyd(n);
    cin >> u >> v;
    //         
    cout << u;
    disp(u,v);
    cout << "-->" << v << endl;
    return 0;
}