結果
問題 | No.614 壊れたキャンパス |
ユーザー | yuppe19 😺 |
提出日時 | 2017-12-26 00:00:08 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 998 ms / 2,000 ms |
コード長 | 2,145 bytes |
コンパイル時間 | 1,266 ms |
コンパイル使用メモリ | 104,356 KB |
実行使用メモリ | 78,432 KB |
最終ジャッジ日時 | 2024-05-10 01:13:47 |
合計ジャッジ時間 | 11,291 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 698 ms
65,584 KB |
testcase_09 | AC | 998 ms
63,664 KB |
testcase_10 | AC | 576 ms
78,432 KB |
testcase_11 | AC | 908 ms
65,576 KB |
testcase_12 | AC | 917 ms
65,444 KB |
testcase_13 | AC | 938 ms
66,148 KB |
testcase_14 | AC | 771 ms
66,792 KB |
testcase_15 | AC | 571 ms
71,452 KB |
testcase_16 | AC | 652 ms
66,760 KB |
testcase_17 | AC | 191 ms
72,896 KB |
testcase_18 | AC | 359 ms
52,744 KB |
testcase_19 | AC | 354 ms
50,608 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:12:27: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 12 | int n, m, k, s, t; scanf("%d%d%d%d%d", &n, &m, &k, &s, &t); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:23:23: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 23 | int a, b, c; scanf("%d%d%d", &a, &b, &c); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <iostream> #include <algorithm> #include <map> #include <queue> using namespace std; using i64 = long long; struct edge { int to; i64 cost; }; int main(void) { constexpr i64 inf = 987654321987654321LL; int n, m, k, s, t; scanf("%d%d%d%d%d", &n, &m, &k, &s, &t); --s, --t; int N = 0; // 頂点数 vector<map<int, int>> mp(n); // 座標圧縮用データ。 mp[a][b] := a棟b階についた連番 vector<vector<int>> route(n); // route[a] := a棟からa+1棟へ廊下がある階のリスト vector<tuple<int, int, int>> dat; // 入力で与えられる m 個の渡り廊下のリスト mp[0] [s] = N++; mp[n-1][t] = N++; route[0] .push_back(s); route[n-1].push_back(t); for(int i=0; i<m; ++i) { int a, b, c; scanf("%d%d%d", &a, &b, &c); --a, --b, --c; dat.emplace_back(a, b, c); if(!mp[a].count(b)) { mp[a][b] = N++; route[a].push_back(b); } if(!mp[a+1].count(c)) { mp[a+1][c] = N++; route[a+1].push_back(c); } } vector<vector<edge>> G(N); for(int i=0; i<m; ++i) { int a, b, c; tie(a, b, c) = dat[i]; G[mp[a][b]].push_back(edge{mp[a+1][c], 0}); } for(int a=0; a<n; ++a) { sort(begin(route[a]), end(route[a])); for(int k=0, size=route[a].size(); k<size-1; ++k) { int b0 = route[a][k], b1 = route[a][k+1]; if(b0 == b1) { continue; } int u = mp[a][b0], v = mp[a][b1]; G[u].push_back(edge{v, b1-b0}); G[v].push_back(edge{u, b1-b0}); } } // ここからダイクストラ vector<i64> cost(N, inf); vector<bool> seen(N, false); cost[mp[0][s]] = 0; priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> pq; // コスト、点番号 pq.emplace(0, mp[0][s]); while(!pq.empty()) { i64 _; int v; tie(_, v) = pq.top(); pq.pop(); if(seen[v]) { continue; } seen[v] = true; for(edge e : G[v]) { if(cost[e.to] > cost[v] + e.cost) { cost[e.to] = cost[v] + e.cost; pq.emplace(cost[e.to], e.to); } } } i64 res = cost[mp[n-1][t]]; if(res == inf) { res = -1; } printf("%lld\n", res); return 0; }