結果
問題 | No.1995 CHIKA Road |
ユーザー | MasKoaTS |
提出日時 | 2022-02-19 17:10:23 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 589 ms / 2,000 ms |
コード長 | 1,390 bytes |
コンパイル時間 | 1,250 ms |
コンパイル使用メモリ | 105,340 KB |
実行使用メモリ | 39,592 KB |
最終ジャッジ日時 | 2023-09-17 05:09:47 |
合計ジャッジ時間 | 9,129 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,384 KB |
testcase_02 | AC | 1 ms
4,384 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 18 ms
5,408 KB |
testcase_07 | AC | 77 ms
10,740 KB |
testcase_08 | AC | 2 ms
4,380 KB |
testcase_09 | AC | 2 ms
4,384 KB |
testcase_10 | AC | 83 ms
11,020 KB |
testcase_11 | AC | 589 ms
39,592 KB |
testcase_12 | AC | 337 ms
24,736 KB |
testcase_13 | AC | 150 ms
15,300 KB |
testcase_14 | AC | 159 ms
16,100 KB |
testcase_15 | AC | 515 ms
35,384 KB |
testcase_16 | AC | 35 ms
6,832 KB |
testcase_17 | AC | 197 ms
18,408 KB |
testcase_18 | AC | 367 ms
28,304 KB |
testcase_19 | AC | 363 ms
28,300 KB |
testcase_20 | AC | 169 ms
17,048 KB |
testcase_21 | AC | 151 ms
15,980 KB |
testcase_22 | AC | 332 ms
26,924 KB |
testcase_23 | AC | 83 ms
11,048 KB |
testcase_24 | AC | 280 ms
23,988 KB |
testcase_25 | AC | 40 ms
7,756 KB |
testcase_26 | AC | 98 ms
12,252 KB |
testcase_27 | AC | 278 ms
23,376 KB |
testcase_28 | AC | 153 ms
15,828 KB |
testcase_29 | AC | 351 ms
27,532 KB |
testcase_30 | AC | 40 ms
7,484 KB |
testcase_31 | AC | 18 ms
5,120 KB |
testcase_32 | AC | 54 ms
8,900 KB |
testcase_33 | AC | 270 ms
22,940 KB |
testcase_34 | AC | 19 ms
5,660 KB |
testcase_35 | AC | 93 ms
11,612 KB |
testcase_36 | AC | 111 ms
12,960 KB |
testcase_37 | AC | 313 ms
25,752 KB |
testcase_38 | AC | 209 ms
19,684 KB |
testcase_39 | AC | 16 ms
5,264 KB |
ソースコード
#include <iostream> #include <vector> #include <queue> #include <set> #include <map> #define rep(i, l, n) for (int i = (l); i < (n); i++) using namespace std; using Pair = pair<int, int>; template <class T> using V = vector<T>; template <class T> using VV = V<V<T> >; const int inf = 2000000000; int dijkstra(int N, int start, int goal, VV<Pair>&route) { V<int> path(N, inf); priority_queue<Pair, V<Pair>, greater<Pair> > pq; pq.push({ 0,start }); while (pq.empty() == false) { Pair p = pq.top(); pq.pop(); int d = p.first; int v = p.second; if (path[v] <= d) { continue; } if (v == goal) { return d; } path[v] = d; for(auto& p : route[v]){ pq.push({ d + p.second,p.first }); } } return -1; } int main(void) { int n, m; cin >> n >> m; set<int> st = { 1,n }; VV<int> edge(m); rep(i, 0, m) { int a, b; cin >> a >> b; st.insert(a); st.insert(b); edge[i] = { a,b }; } int N = st.size(); int cnt = 0, last = -1; map<int, int> mp; VV<Pair> route(N, V<Pair>(0)); for (auto itr = st.begin(); itr != st.end(); itr++) { mp[*itr] = cnt; cnt++; if (last > -1) { route[mp[last]].push_back({ mp[*itr],2 * (*itr) - 2 * last }); } last = *itr; } for (auto& e : edge) { int a = mp[e[0]], b = mp[e[1]]; route[a].push_back({ b,2 * e[1] - 2 * e[0] - 1 }); } int ans = dijkstra(N, 0, N - 1, route); cout << ans << endl; return 0; }