結果
問題 |
No.160 最短経路のうち辞書順最小
|
ユーザー |
|
提出日時 | 2016-06-21 19:06:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,210 bytes |
コンパイル時間 | 1,244 ms |
コンパイル使用メモリ | 108,120 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-11 18:34:38 |
合計ジャッジ時間 | 2,246 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 4 |
other | WA * 26 |
ソースコード
#include <iostream> #include <queue> #include <map> #include <list> #include <vector> #include <string> #include <limits> #include <cassert> #include <fstream> #include <cstring> #include <bitset> #include <iomanip> #include <algorithm> #include <functional> #include <cstdio> #include <ciso646> #include <array> using namespace std; #define FOR(i,a,b) for (int i=(a);i<(b);i++) #define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--) #define REP(i,n) for (int i=0;i<(n);i++) #define RREP(i,n) for (int i=(n)-1;i>=0;i--) #define inf 0x3f3f3f3f #define CLEAR(a) a = decltype(a)() #define MP make_pair #define ALL(a) (a).begin(),(a).end() #define pii pair<int ,int> #define pcc pair<char,char> #define pic pair<int,char> #define pci pair<char,int> #define VS vector<string> #define VI vector<int> #define DEBUG(x) cout<<#x<<": "<<x<<endl #define pi 2*acos(0.0) #define INFILE() freopen("in.txt","r",stdin) #define OUTFILE() freopen("out.txt","w",stdout) #define ll long long #define ull unsigned long long #define eps 1e-14 struct edge { int to; int c; edge(int t_, int c_):to(t_), c(c_){} edge():to(0), c(0){} }; const int MAX_V = 200; int V; vector<edge> G[MAX_V]; int d[MAX_V]; int pre[MAX_V]; void dijkstra(int s) { priority_queue<pii, vector<pii>, greater<pii> > que; memset(d, inf, sizeof(d)); d[s] = 0; que.push(pii(0, s)); while (not que.empty()) { pii p = que.top(); que.pop(); int v = p.second; if (d[v] < p.first) continue; for (auto &e : G[v]) { if (d[e.to] > d[v] + e.c) { d[e.to] = d[v] + e.c; pre[e.to] = v; que.push(pii(d[e.to], e.to)); } if (d[e.to] == d[v] + e.c) { if (v < pre[e.to]) pre[e.to] = v; } } } } vector<int> get_path(int s, int t) { vector<int> path; for (; t != s; t = pre[t]) path.push_back(t); return path; } int main(void) { int N, M, S, Goal; cin >> N >> M >> S >> Goal; REP(i, M) { int a, b, c; cin >> a >> b >> c; G[a].emplace_back(b, c); G[b].emplace_back(a, c); } for (auto &a : G) { sort(ALL(a), [](edge left, edge right) {return left.to < right.to; }); } dijkstra(Goal); vector<int> v = get_path(Goal, S); for (auto &a : v) { cout << a << " "; } cout << Goal << endl; cout << endl; return 0; }