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;
}