No.160 最短経路のうち辞書順最小
No.160 最短経路のうち辞書順最小 - yukicoder
- 経路復元問題
- N<=200 程度なのでワーシャルフロイドで解ける。ダイクストラならもうちょい面倒かも。
- 経路があるかどうかは cost[c][i] をみればよい。
class LexicographicOrderShortestPath { public: void solve(void) { int N,M,S,G; cin>>N>>M>>S>>G; const int inf = 1<<30; vector<vector<ll>> cost(N,vector<ll>(N,0)); vector<vector<ll>> dist(N,vector<ll>(N,inf)); REP(i,N) dist[i][i] = 0; REP(i,M) { int a,b,c; cin>>a>>b>>c; dist[a][b] = dist[b][a] = c; cost[a][b] = cost[b][a] = c; } REP(k,N) REP(i,N) REP(j,N) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); int c = S; cout<<c<<" "; while (c != G) { REP(i,N) { if (c == i) continue; // 経路があるかどうかは cost[c][i] を見ればよい if (dist[c][G] == cost[c][i]+dist[i][G] && cost[c][i] > 0) { c = i; if (c == G) cout<<c<<endl; else cout<<c<<" "; break; } } } } };