結果
問題 |
No.160 最短経路のうち辞書順最小
|
ユーザー |
![]() |
提出日時 | 2020-02-02 23:41:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 13 ms / 5,000 ms |
コード長 | 1,761 bytes |
コンパイル時間 | 1,974 ms |
コンパイル使用メモリ | 178,836 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-18 21:32:54 |
合計ジャッジ時間 | 3,038 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define each(i, c) for (auto& i : c) typedef long long ll; typedef unsigned long long ull; const ll MOD = 1e9+7; template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << ": " << p.second << ")"; return os; } template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ", "; os << ")"; return os; } template<typename K, typename V> ostream& operator << (ostream& os, map<K, V> m) { os << "{"; each (i, m) os << i << ", "; os << "}"; return os; } int main() { ll n, m, s, g; cin >> n >> m >> s >> g; vector<vector<ll>> graph(n, vector<ll>()); vector<vector<ll>> cost(n, vector<ll>(n, 0)); vector<ll> dest(n, 1e18); for (ll i = 0; i < m; ++i) { ll a, b, c; cin >> a >> b >> c; graph[a].push_back(b); graph[b].push_back(a); cost[a][b] = c; cost[b][a] = c; } swap(s, g); priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q; dest[s] = 0; q.push(pair<ll, ll>(0, s)); while (!q.empty()) { auto p = q.top(); q.pop(); auto c = p.first; auto i = p.second; if (dest[i] < c) continue; each (j, graph[i]) { auto nc = cost[i][j] + c; if (nc >= dest[j]) continue; dest[j] = nc; q.push(pair<ll, ll>(nc, j)); } } ll cur = g; vector<ll> ans = {cur}; while (cur != s) { ll next = 1e18; each (i, graph[cur]) { if (dest[cur] == dest[i] + cost[cur][i]) { next = min(next, i); } } cur = next; ans.push_back(cur); } for (ll i = 0; i < ans.size(); ++i) { cout << ans[i]; if (i == ans.size()-1) cout << endl; else cout << " "; } return 0; }