結果
問題 |
No.160 最短経路のうち辞書順最小
|
ユーザー |
![]() |
提出日時 | 2016-07-28 16:46:54 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 25 ms / 5,000 ms |
コード長 | 1,139 bytes |
コンパイル時間 | 1,929 ms |
コンパイル使用メモリ | 176,456 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-06 18:11:07 |
合計ジャッジ時間 | 3,205 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> #define _overload(_1,_2,_3,name,...) name #define _rep(i,n) _range(i,0,n) #define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i) #define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__) #define _all(arg) begin(arg),end(arg) template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0; } template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0; } using namespace std; using vi=vector<int>; const int INF=1<<28; int S, G; int main() { int N, M; cin >> N >> M >> S >> G; vector<vi> edge(N, vi(N, INF)); vector<vi> dist; rep(i, M) { int a, b, c; cin >> a >> b >> c; edge[a][b] = edge[b][a] = c; } rep(i, N) { edge[i][i] = 0; } dist = edge; rep(k, N) rep(i, N) rep(j, N) { chmin(dist[i][j], dist[i][k] + dist[k][j]); } int cur = S; vector<int> res; res.push_back(S); while (cur != G) { rep(i, N) { if (i == cur) continue; if(dist[S][cur] + edge[cur][i] + dist[i][G] == dist[S][G]) { cur = i; res.push_back(i); break; } } } rep(i, res.size()-1) { cout << res[i] << " "; } cout << res[res.size()-1] << endl; return 0; }