結果
問題 | No.1812 Uribo Road |
ユーザー |
![]() |
提出日時 | 2024-04-02 14:29:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 95 ms / 5,000 ms |
コード長 | 3,612 bytes |
コンパイル時間 | 2,893 ms |
コンパイル使用メモリ | 221,460 KB |
最終ジャッジ日時 | 2025-02-20 19:39:39 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
#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;}