結果
問題 |
No.160 最短経路のうち辞書順最小
|
ユーザー |
![]() |
提出日時 | 2016-03-23 17:18:24 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 143 ms / 5,000 ms |
コード長 | 1,660 bytes |
コンパイル時間 | 982 ms |
コンパイル使用メモリ | 96,420 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-01 21:33:44 |
合計ジャッジ時間 | 2,491 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
/* -*- coding: utf-8 -*- * * 160.cc: No.160 最短経路のうち辞書順最小 - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 200; const int INF = 1 << 30; /* typedef */ typedef vector<int> vi; typedef queue<int> qi; typedef pair<int,int> pii; typedef vector<pii> vpii; /* global variables */ vpii nbrs[MAX_N]; vi pths[MAX_N]; int dists[MAX_N]; /* subroutines */ /* main */ int main() { int n, m, st, gl; cin >> n >> m >> st >> gl; for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; nbrs[a].push_back(pii(b, c)); nbrs[b].push_back(pii(a, c)); } for (int i = 0; i < n; i++) dists[i] = INF; dists[st] = 0; priority_queue<pii> q; q.push(pii(0, st)); while (! q.empty()) { pii u = q.top(); q.pop(); int ud = -u.first, ui = u.second; if (ui == gl) break; vpii &nbru = nbrs[ui]; vi pthv(pths[ui]); for (vpii::iterator vit = nbru.begin(); vit != nbru.end(); vit++) { int vi = vit->first, vd = ud + vit->second; pthv.push_back(vi); if (dists[vi] > vd || (dists[vi] == vd && pths[vi] > pthv)) { dists[vi] = vd; pths[vi] = pthv; q.push(pii(-vd, vi)); } pthv.pop_back(); } } printf("%d", st); for (int i = 0; i < pths[gl].size(); i++) printf(" %d", pths[gl][i]); putchar('\n'); return 0; }