結果
問題 | No.1812 Uribo Road |
ユーザー | SSRS |
提出日時 | 2022-01-14 21:46:03 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 409 ms / 5,000 ms |
コード長 | 2,108 bytes |
コンパイル時間 | 1,805 ms |
コンパイル使用メモリ | 187,028 KB |
実行使用メモリ | 18,152 KB |
最終ジャッジ日時 | 2023-08-12 18:52:07 |
合計ジャッジ時間 | 7,900 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge10 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 298 ms
4,612 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,376 KB |
testcase_07 | AC | 22 ms
4,376 KB |
testcase_08 | AC | 9 ms
4,380 KB |
testcase_09 | AC | 10 ms
4,376 KB |
testcase_10 | AC | 8 ms
4,376 KB |
testcase_11 | AC | 4 ms
4,380 KB |
testcase_12 | AC | 384 ms
10,868 KB |
testcase_13 | AC | 348 ms
17,764 KB |
testcase_14 | AC | 378 ms
18,152 KB |
testcase_15 | AC | 63 ms
4,412 KB |
testcase_16 | AC | 75 ms
5,420 KB |
testcase_17 | AC | 213 ms
5,168 KB |
testcase_18 | AC | 334 ms
4,904 KB |
testcase_19 | AC | 393 ms
6,484 KB |
testcase_20 | AC | 387 ms
6,284 KB |
testcase_21 | AC | 409 ms
11,944 KB |
testcase_22 | AC | 406 ms
11,880 KB |
testcase_23 | AC | 46 ms
4,380 KB |
testcase_24 | AC | 2 ms
4,376 KB |
testcase_25 | AC | 20 ms
4,376 KB |
testcase_26 | AC | 5 ms
4,376 KB |
testcase_27 | AC | 159 ms
4,376 KB |
testcase_28 | AC | 31 ms
4,424 KB |
testcase_29 | AC | 1 ms
4,376 KB |
testcase_30 | AC | 17 ms
4,376 KB |
testcase_31 | AC | 323 ms
4,752 KB |
testcase_32 | AC | 20 ms
4,380 KB |
testcase_33 | AC | 341 ms
7,428 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ int N, M, K; cin >> N >> M >> K; vector<int> R(K); for (int i = 0; i < K; i++){ cin >> R[i]; R[i]--; } vector<int> A(M), B(M), C(M); for (int i = 0; i < M; i++){ cin >> A[i] >> B[i] >> C[i]; A[i]--; B[i]--; } vector<vector<pair<int, int>>> E(N); for (int i = 0; i < M; i++){ E[A[i]].push_back(make_pair(C[i], B[i])); E[B[i]].push_back(make_pair(C[i], A[i])); } vector<int> id; id.push_back(0); id.push_back(N - 1); for (int i = 0; i < K; i++){ id.push_back(A[R[i]]); id.push_back(B[R[i]]); } int V = id.size(); vector<vector<int>> d(V, vector<int>(V)); for (int i = 0; i < V; i++){ vector<int> d2(N, -1); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push(make_pair(0, id[i])); while (!pq.empty()){ int c = pq.top().first; int v = pq.top().second; pq.pop(); if (d2[v] == -1){ d2[v] = c; for (auto P : E[v]){ int w = P.second; if (d2[w] == -1){ pq.push(make_pair(c + P.first, w)); } } } } for (int j = 0; j < V; j++){ d[i][j] = d2[id[j]]; } } vector<vector<int>> T(V, vector<int>(V, -1)); for (int i = 0; i < K; i++){ d[i * 2 + 2][i * 2 + 3] = C[R[i]]; d[i * 2 + 3][i * 2 + 2] = C[R[i]]; T[i * 2 + 2][i * 2 + 3] = i; T[i * 2 + 3][i * 2 + 2] = i; } vector<vector<int>> d2(1 << K, vector<int>(V, -1)); priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq; pq.push(make_tuple(0, 0, 0)); while (!pq.empty()){ int c = get<0>(pq.top()); int s = get<1>(pq.top()); int v = get<2>(pq.top()); pq.pop(); if (d2[s][v] == -1){ d2[s][v] = c; for (int i = 0; i < V; i++){ int s2 = s; if (T[v][i] != -1){ s2 |= 1 << T[v][i]; } if (d2[s2][i] == -1){ pq.push(make_tuple(c + d[v][i], s2, i)); } } } } cout << d2[(1 << K) - 1][1] << endl; }