結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー |
![]() |
提出日時 | 2016-06-21 18:13:28 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,565 bytes |
コンパイル時間 | 1,600 ms |
コンパイル使用メモリ | 179,576 KB |
実行使用メモリ | 10,148 KB |
最終ジャッジ日時 | 2024-10-11 18:29:25 |
合計ジャッジ時間 | 14,889 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 4 |
other | RE * 23 TLE * 1 -- * 2 |
コンパイルメッセージ
main.cpp: In function ‘bool {anonymous}::operator<(const {anonymous}::State&, const {anonymous}::State&)’: main.cpp:56:5: warning: no return statement in function returning non-void [-Wreturn-type] 56 | } | ^ main.cpp: In function ‘int {anonymous}::calc(std::vector<int>&, std::vector<std::vector<{anonymous}::Edge> >&)’: main.cpp:86:5: warning: no return statement in function returning non-void [-Wreturn-type] 86 | } | ^
ソースコード
#include <bits/stdc++.h> using namespace std; namespace { typedef double real; typedef long long ll; template<class T> ostream& operator<<(ostream& os, const vector<T>& vs) { if (vs.empty()) return os << "[]"; os << vs[0]; for (int i = 1; i < vs.size(); i++) os << " " << vs[i]; return os; } template<class T> istream& operator>>(istream& is, vector<T>& vs) { for (auto it = vs.begin(); it != vs.end(); it++) is >> *it; return is; } struct Edge { int from, to, cost; Edge(int from, int to, int cost) : from(from), to(to), cost(cost) {} }; int N, M, S, G; vector<vector<Edge>> Graph; void input() { cin >> N >> M >> S >> G; Graph.clear(); Graph.resize(N); for (int i = 0; i < M; i++) { int a, b, c; cin >> a >> b >> c; Graph[a].push_back(Edge(a, b, c)); Graph[b].push_back(Edge(b, a, c)); } } typedef pair<int, vector<int>> C; const int INF = 1<<28; const C INF_C = make_pair(INF, vector<int>(1, 1000)); struct State { int v; C cost; State() {} State(int v, C cost) : v(v), cost(cost) {} }; bool operator<(const State& a, const State& b) { if (a.cost.first == b.cost.first) { a.cost.second > b.cost.second; } else { a.cost.first > b.cost.first; } } struct State0 { int v, cost; State0(int v, int cost) : v(v), cost(cost) {} }; bool operator<(const State0& a, const State0& b) { return a.cost > b.cost; } int calc(vector<int>& D, vector<vector<Edge>>& P) { priority_queue<State0> PQ; D[S] = 0; PQ.push(State0(S, D[S])); while (not PQ.empty()) { State0 s = PQ.top(); PQ.pop(); int v = s.v; int cost = s.cost; for (int i = 0; i < Graph[v].size(); i++) { const Edge& e = Graph[v][i]; if (D[e.to] > cost + e.cost) { D[e.to] = cost + e.cost; PQ.push(State0(e.to, cost + e.cost)); P[e.to].clear(); P[e.to].push_back(e); } if (D[e.to] == cost + e.cost) { P[e.to].push_back(e); } } } } vector<int> D; vector<vector<Edge>> P; ostream& operator<<(ostream& os, const Edge& e) { return os << "(" << e.from << "->" << e.to << ")"; } vector<vector<int>> memo; vector<int> dfs(int v) { if (v == S) return vector<int>(1, S); if (memo[v][0] >= 0) return memo[v]; vector<int> ret; ret.push_back(INF); for (int i = 0; i < P[v].size(); i++) { // e.to縺後>縺セ縺ソ縺ヲ繧久 // e.from縺後″縺溘∪縺。 const Edge& e = P[v][i]; auto p = dfs(e.from); p.push_back(v); ret = min(ret, p); } return memo[v] = ret; } void solve() { D.clear(); D.resize(N, INF); P.clear(); P.resize(N); calc(D, P); /* for (int i = 0; i < N; i++) { cout << i << " -> " << P[i] << endl; } cout << endl; */ memo.clear(); memo.resize(N, vector<int>(1, -1)); cout << dfs(G) << endl; } } int main() { vector<int> a = {4, 1}; vector<int> b = {4, 3}; input(); solve(); return 0; }