結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー |
![]() |
提出日時 | 2015-03-01 23:52:08 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,771 bytes |
コンパイル時間 | 1,392 ms |
コンパイル使用メモリ | 170,132 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-24 00:42:37 |
合計ジャッジ時間 | 2,347 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 8 WA * 18 |
ソースコード
#include <bits/stdc++.h> #define REP(i, x, n) for(int i = x; i < (int)(n); i++) #define rep(i, n) REP(i, 0, n) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define F first #define S second #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> P; const int INF = 1 << 30; struct State { int pos, dist; State(int p, int d): pos(p), dist(d) {} bool operator < (const State &stt) const { return stt.dist < dist; } }; struct Edge { int to, dist; Edge(int t, int d): to(t), dist(d) {} }; int N, M, S, G; vector<Edge> edge[200]; int prevN[200]; int minDist[200]; void solve() { rep(i, N) { prevN[i] = -1; minDist[i] = INF; } priority_queue<State> pq; pq.push(State(S, 0)); minDist[S] = 0; while(!pq.empty()) { State stt = pq.top(); pq.pop(); if(stt.pos == G) break; rep(i, edge[stt.pos].size()) { int to = edge[stt.pos][i].to; int dist = edge[stt.pos][i].dist; if(minDist[to] > minDist[stt.pos] + dist || (minDist[to] == minDist[stt.pos] + dist && prevN[to] > stt.pos)) { prevN[to] = stt.pos; minDist[to] = minDist[stt.pos] + dist; pq.push(State(to, minDist[to])); } } } vector<int> ans; ans.push_back(G); for(int p = prevN[G]; p != S; p = prevN[p]) { ans.push_back(p); } ans.push_back(S); reverse(all(ans)); rep(i, ans.size()) { if(i) cout << ' '; cout << ans[i]; } cout << endl; } int main() { // ios_base::sync_with_stdio(false); cin >> N >> M >> S >> G; rep(i, M) { int a, b, c; cin >> a >> b >> c; edge[a].push_back(Edge(b, c)); edge[b].push_back(Edge(a, c)); } solve(); return 0; }