結果
問題 |
No.160 最短経路のうち辞書順最小
|
ユーザー |
|
提出日時 | 2020-04-12 18:58:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 5,000 ms |
コード長 | 2,334 bytes |
コンパイル時間 | 1,628 ms |
コンパイル使用メモリ | 140,884 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-22 05:29:44 |
合計ジャッジ時間 | 2,986 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <cstdio> #include <iostream> #include <string> #include <sstream> #include <stack> #include <algorithm> #include <cmath> #include <queue> #include <map> #include <set> #include <cstdlib> #include <bitset> #include <tuple> #include <assert.h> #include <deque> #include <bitset> #include <iomanip> #include <limits> #include <chrono> #include <random> #include <array> #include <unordered_map> #include <functional> #include <complex> #include <numeric> template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } constexpr long long MAX = 5100000; constexpr long long INF = 1LL << 60; constexpr int inf = 1 << 28; //constexpr long long mod = 1000000007LL; //constexpr long long mod = 998244353LL; using namespace std; typedef unsigned long long ull; typedef long long ll; void dijkstra(ll start, vector<vector<pair<int, ll>>>& graph, vector<ll>& dist) { dist[start] = 0; priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq; vector<bool> used(dist.size(), false); pq.push(make_pair(0, start)); while (!pq.empty()) { ll d, node; tie(d, node) = pq.top(); pq.pop(); if (used[node]) continue; used[node] = true; for (pair<ll, ll> element : graph[node]) { ll new_d, new_node; tie(new_node, new_d) = element; new_d += d; if (new_d < dist[new_node]) { dist[new_node] = new_d; pq.push(make_pair(dist[new_node], new_node)); } } } } int main() { /* cin.tie(nullptr); ios::sync_with_stdio(false); */ int n, m, st, go; scanf("%d %d %d %d", &n, &m, &st, &go); vector<vector<pair<int, ll>>> g(n); for (int i = 0; i < m; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); g[a].emplace_back(b, c); g[b].emplace_back(a, c); } vector<ll> d(n, INF); dijkstra(go, g, d); queue<int> q; q.push(st); vector<int> res; while (!q.empty()) { int cur = q.front(); q.pop(); res.push_back(cur); if (cur == go) break; vector<pair<ll, int>> vp; for (auto next : g[cur]) { vp.emplace_back(next.second + d[next.first], next.first); } sort(vp.begin(), vp.end()); q.push(vp[0].second); } for (int i = 0; i < res.size(); i++) { cout << res[i]; if (i + 1 == res.size()) cout << "\n"; else cout << " "; } return 0; }