結果
問題 |
No.1812 Uribo Road
|
ユーザー |
![]() |
提出日時 | 2022-01-14 21:46:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 441 ms / 5,000 ms |
コード長 | 2,108 bytes |
コンパイル時間 | 2,064 ms |
コンパイル使用メモリ | 189,700 KB |
実行使用メモリ | 16,916 KB |
最終ジャッジ日時 | 2024-11-20 09:13:09 |
合計ジャッジ時間 | 8,031 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
#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; }