結果
問題 |
No.160 最短経路のうち辞書順最小
|
ユーザー |
|
提出日時 | 2015-08-18 20:01:03 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 258 ms / 5,000 ms |
コード長 | 2,206 bytes |
コンパイル時間 | 1,852 ms |
コンパイル使用メモリ | 178,664 KB |
実行使用メモリ | 6,968 KB |
最終ジャッジ日時 | 2024-07-18 10:14:51 |
合計ジャッジ時間 | 2,674 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> #define rep(i, a) for (int i = 0; i < (a); i++) #define rep2(i, a, b) for (int i = (a); i < (b); i++) #define repr(i, a) for (int i = (a) - 1; i >= 0; i--) #define repr2(i, a, b) for (int i = (b) - 1; i >= (a); i--) using namespace std; typedef long long ll; const ll inf = 1e9; const ll mod = 1e9 + 7; typedef pair<int, int> P; // to, length typedef tuple<int, vector<int>, int> P3; // dist, path, curr typedef pair<int, vector<int>> Q; struct comparer : public binary_function<P3, P3, bool> { bool operator()(const P3 &a, const P3 &b) const { if (get<0>(a) != get<0>(b)) { return get<0>(a) > get<0>(b); } auto &l = get<1>(a); auto &r = get<1>(b); return lexicographical_compare(r.begin(), r.end(), l.begin(), l.end()); } }; int N, M, S, T; vector<P> G[200]; Q dp[200]; ostream &operator <<(ostream &os, const vector<int> &v) { rep (i, v.size()) { if (i) cout << " "; cout << v[i]; } return os; } int main() { cin >> N >> M >> S >> T; rep (i, M) { int a, b, c; cin >> a >> b >> c; G[a].emplace_back(b, c); G[b].emplace_back(a, c); } rep (i, N) dp[i].first = inf; priority_queue<P3, vector<P3>, comparer> q; q.emplace(0, vector<int>(1, S), S); dp[S] = Q(0, vector<int>(1, S)); while (!q.empty()) { P3 p = q.top(); q.pop(); int curr = get<2>(p); for (auto e : G[curr]) { if (dp[e.first].first > dp[curr].first + e.second) { dp[e.first].first = dp[curr].first + e.second; dp[e.first].second = dp[curr].second; dp[e.first].second.push_back(e.first); q.emplace(dp[e.first].first, dp[e.first].second, e.first); } else if (dp[e.first].first == dp[curr].first + e.second) { auto &l = dp[e.first].second; auto r = dp[curr].second; r.push_back(e.first); if (lexicographical_compare(r.begin(), r.end(), l.begin(), l.end()) > 0) { l = r; q.emplace(dp[e.first].first, l, e.first); } } } } cout << dp[T].second << endl; return 0; }