結果
問題 | No.1812 Uribo Road |
ユーザー | eve__fuyuki |
提出日時 | 2024-04-02 14:29:38 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 92 ms / 5,000 ms |
コード長 | 3,612 bytes |
コンパイル時間 | 2,685 ms |
コンパイル使用メモリ | 230,916 KB |
実行使用メモリ | 7,120 KB |
最終ジャッジ日時 | 2024-09-30 23:13:41 |
合計ジャッジ時間 | 4,948 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 8 ms
6,816 KB |
testcase_04 | AC | 2 ms
6,820 KB |
testcase_05 | AC | 2 ms
6,820 KB |
testcase_06 | AC | 2 ms
6,820 KB |
testcase_07 | AC | 2 ms
6,816 KB |
testcase_08 | AC | 2 ms
6,816 KB |
testcase_09 | AC | 3 ms
6,816 KB |
testcase_10 | AC | 3 ms
6,816 KB |
testcase_11 | AC | 3 ms
6,820 KB |
testcase_12 | AC | 41 ms
6,816 KB |
testcase_13 | AC | 18 ms
6,820 KB |
testcase_14 | AC | 17 ms
6,816 KB |
testcase_15 | AC | 28 ms
6,820 KB |
testcase_16 | AC | 26 ms
6,816 KB |
testcase_17 | AC | 75 ms
6,816 KB |
testcase_18 | AC | 18 ms
6,816 KB |
testcase_19 | AC | 92 ms
7,120 KB |
testcase_20 | AC | 90 ms
7,116 KB |
testcase_21 | AC | 71 ms
7,116 KB |
testcase_22 | AC | 55 ms
7,116 KB |
testcase_23 | AC | 4 ms
6,820 KB |
testcase_24 | AC | 2 ms
6,820 KB |
testcase_25 | AC | 13 ms
6,816 KB |
testcase_26 | AC | 3 ms
6,816 KB |
testcase_27 | AC | 13 ms
6,816 KB |
testcase_28 | AC | 24 ms
6,820 KB |
testcase_29 | AC | 2 ms
6,820 KB |
testcase_30 | AC | 4 ms
6,816 KB |
testcase_31 | AC | 48 ms
6,820 KB |
testcase_32 | AC | 3 ms
6,820 KB |
testcase_33 | AC | 23 ms
6,816 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; void fast_io() { ios::sync_with_stdio(false); std::cin.tie(nullptr); } int main() { fast_io(); 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<tuple<int, int, int>> edges; vector<vector<pair<int, int>>> g(n); for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; a--, b--; g[a].push_back({b, c}); g[b].push_back({a, c}); edges.push_back({a, b, c}); } vector<pair<int, int>> need_edges; vector<int> w; vector<int> vs; for (int i = 0; i < k; i++) { auto [a, b, c] = edges[r[i]]; need_edges.push_back({a, b}); vs.push_back(a); vs.push_back(b); w.push_back(c); } need_edges.push_back({0, 0}); need_edges.push_back({n - 1, n - 1}); vs.push_back(0); vs.push_back(n - 1); w.push_back(0); w.push_back(0); sort(vs.begin(), vs.end()); vs.erase(unique(vs.begin(), vs.end()), vs.end()); int N = vs.size(); vector<vector<int>> d(N, vector<int>(N)); using pii = pair<int, int>; for (int i = 0; i < N; i++) { vector<int> dist(n, 1e9); vector<bool> vis(n); dist[vs[i]] = 0; priority_queue<pii, vector<pii>, greater<pii>> pq; pq.push({0, vs[i]}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (vis[u]) { continue; } vis[u] = true; for (auto [v, w] : g[u]) { if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } for (int j = 0; j < N; j++) { d[i][j] = dist[vs[j]]; } } for (int i = 0; i < need_edges.size(); i++) { auto [a, b] = need_edges[i]; need_edges[i] = {lower_bound(vs.begin(), vs.end(), a) - vs.begin(), lower_bound(vs.begin(), vs.end(), b) - vs.begin()}; } vector<vector<vector<int>>> dp(1 << k, vector<vector<int>>(k, vector<int>(2, 1e9))); for (int i = 0; i < k; i++) { dp[1 << i][i][0] = d[0][need_edges[i].second] + w[i]; dp[1 << i][i][1] = d[0][need_edges[i].first] + w[i]; } for (int msk = 0; msk < (1 << k); msk++) { for (int i = 0; i < k; i++) { if (msk & (1 << i)) { for (int j = 0; j < k; j++) { if (!(msk & (1 << j))) { for (int fi = 0; fi < 2; fi++) { for (int fj = 0; fj < 2; fj++) { int v1 = (fi ? need_edges[i].second : need_edges[i].first); int v2 = (fj ? need_edges[j].second : need_edges[j].first); dp[msk | (1 << j)][j][1 - fj] = min(dp[msk | (1 << j)][j][1 - fj], dp[msk][i][fi] + d[v1][v2] + w[j]); } } } } } } } int ans = 1e9; for (int i = 0; i < k; i++) { ans = min(ans, dp[(1 << k) - 1][i][0] + d[need_edges[i].first][N - 1]); ans = min(ans, dp[(1 << k) - 1][i][1] + d[need_edges[i].second][N - 1]); } cout << ans << endl; }