結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー |
![]() |
提出日時 | 2016-06-21 17:50:11 |
言語 | C++11 (gcc 11.4.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 3,414 bytes |
コンパイル時間 | 1,594 ms |
コンパイル使用メモリ | 179,688 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-11 18:26:00 |
合計ジャッジ時間 | 6,138 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | RE | - |
testcase_01 | RE | - |
testcase_02 | RE | - |
testcase_03 | RE | - |
testcase_04 | RE | - |
testcase_05 | RE | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | RE | - |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | RE | - |
testcase_20 | RE | - |
testcase_21 | RE | - |
testcase_22 | RE | - |
testcase_23 | RE | - |
testcase_24 | RE | - |
testcase_25 | RE | - |
testcase_26 | RE | - |
testcase_27 | RE | - |
testcase_28 | RE | - |
testcase_29 | RE | - |
コンパイルメッセージ
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>&)’: main.cpp:81:5: warning: no return statement in function returning non-void [-Wreturn-type] 81 | } | ^
ソースコード
#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) { 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)); } } } } void solve() { vector<int> D0(N, INF); int LIM = calc(D0); priority_queue<State> PQ; vector<C> D(N, INF_C); D[S] = make_pair(0, vector<int>(1, S)); for (int i = 0; i < N; i++) D[i].first = D0[i]; PQ.push(State(S, D[S])); while (not PQ.empty()) { State s = PQ.top(); PQ.pop(); int v = s.v; int cost = s.cost.first; //cout << v << " " << cost << endl; vector<int>& path = s.cost.second; for (int i = 0; i < Graph[v].size(); i++) { const Edge& e = Graph[v][i]; State nstate; path.push_back(e.to); if (D[e.to].first > cost + e.cost || (D[e.to].first == cost + e.cost && D[e.to].second > path)) { State nstate; nstate.v = e.to; nstate.cost = make_pair(cost + e.cost, path); D[e.to] = nstate.cost; PQ.push(nstate); } path.pop_back(); } } cout << D[G].second << endl; } } int main() { input(); solve(); return 0; }