結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー |
![]() |
提出日時 | 2015-12-28 09:33:49 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 14 ms / 5,000 ms |
コード長 | 1,514 bytes |
コンパイル時間 | 1,286 ms |
コンパイル使用メモリ | 165,236 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-19 07:35:34 |
合計ジャッジ時間 | 2,525 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> typedef long long ll; typedef unsigned long long ull; #define FOR(i,a,b) for(int (i)=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define RANGE(vec) (vec).begin(),(vec).end() using namespace std; 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; 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; } } } } }; #if 1 int main(int argc, char *argv[]) { ios::sync_with_stdio(false); auto obj = new LexicographicOrderShortestPath(); obj->solve(); delete obj; return 0; } #endif