結果
問題 |
No.160 最短経路のうち辞書順最小
|
ユーザー |
![]() |
提出日時 | 2020-10-24 17:06:12 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 11 ms / 5,000 ms |
コード長 | 2,176 bytes |
コンパイル時間 | 1,253 ms |
コンパイル使用メモリ | 123,404 KB |
最終ジャッジ日時 | 2025-01-15 15:07:11 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <iomanip> #include <string> #include <stack> #include <queue> #include <map> #include <set> #include <tuple> #include <cstdio> #include <cstdlib> #include <cmath> #include <climits> #include <cassert> #include <cstdint> #include <cctype> #include <numeric> #include <bitset> #include <functional> using namespace std; using ll = long long; using Pll = pair<ll, ll>; using Pii = pair<int, int>; constexpr int INF = 1 << 30; constexpr ll LINF = 1LL << 60; constexpr ll MOD = 1000000007; constexpr long double EPS = 1e-10; constexpr int dyx[4][2] = { { 0, 1}, {-1, 0}, {0,-1}, {1, 0} }; constexpr int MAX_N = 112345; vector<ll> d(MAX_N, LINF); vector<int> path, prevs[MAX_N]; int n, m; priority_queue<Pll, vector<Pll>, greater<Pll> > que; vector<Pll> edges[MAX_N]; void dijkstra(int start, int goal){ d[start] = 0; que.push(Pll(0, start)); while(!que.empty()) { Pll v = que.top(); que.pop(); if(d[v.second] < v.first) continue; for(Pll e: edges[v.second]) { if(d[e.first] > d[v.second] + e.second) { d[e.first] = d[v.second] + e.second; prevs[e.first].clear(); prevs[e.first].push_back(v.second); que.push(Pll(d[e.first], e.first)); } else if(d[e.first] == d[v.second] + e.second) { prevs[e.first].push_back(v.second); } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int start, goal; cin >> n >> m >> start >> goal; int a[m], b[m], c[m]; for(int i=0;i<m;++i) { cin >> a[i] >> b[i] >> c[i]; edges[b[i]].emplace_back(a[i], c[i]); edges[a[i]].emplace_back(b[i], c[i]); } dijkstra(goal, start); if(d[start] == LINF) { cout << -1 << endl; return 0; } int v = start; while(v != goal) { path.push_back(v); v = *min_element(prevs[v].begin(), prevs[v].end()); } path.push_back(goal); for(int i=0;i<path.size();++i) { if(i) cout << " "; cout << path[i]; } cout << endl; return 0; }