結果
問題 | No.1812 Uribo Road |
ユーザー |
![]() |
提出日時 | 2024-11-30 21:42:20 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 205 ms / 5,000 ms |
コード長 | 2,632 bytes |
コンパイル時間 | 2,661 ms |
コンパイル使用メモリ | 223,588 KB |
実行使用メモリ | 9,344 KB |
最終ジャッジ日時 | 2024-11-30 21:42:26 |
合計ジャッジ時間 | 5,724 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>#define inf 1073741823using namespace std;using ll = long long;using Pair = pair<int, int>;vector<int> dijkstra(int sv, vector<vector<Pair> >& graph, int N){vector<int> dp(N, inf);priority_queue<Pair, vector<Pair>, greater<Pair> > pq = {};pq.push({0, sv});while(!pq.empty()){auto[d, v] = pq.top(); pq.pop();if(dp[v] <= d){continue;}dp[v] = d;for(auto&[nv, nd] : graph[v]){pq.push({d + nd, nv});}}return dp;}int main(){int N, M, K; cin >> N >> M >> K;vector<int> R(K);for(auto& x : R){cin >> x; --x;}vector<vector<int> > edges(M);vector<vector<Pair> > graph(N, vector<Pair>({}));for(int i = 0; i < M; ++i){int x, y, z; cin >> x >> y >> z;--x, --y;edges[i] = {x, y, z};graph[x].push_back({y, z});graph[y].push_back({x, z});}unordered_set<int> V = {};V.insert(0), V.insert(N - 1);for(auto r : R){V.insert(edges[r][0]);V.insert(edges[r][1]);}vector<vector<int> > dist(N, vector<int>({}));for(auto& sv : V){dist[sv] = dijkstra(sv, graph, N);}vector<vector<vector<int> > > dp(1 << K, vector<vector<int> >(K, vector<int>(2, inf)));for(int i = 0; i < K; ++i){for(int j = 0; j < 2; ++j){dp[1 << i][i][j] = dist[0][edges[R[i]][j ^ 1]] + edges[R[i]][2];}}for(int bit = 1; bit < (1 << K); ++bit){for(int s = 0; s < K; ++s){if((bit & (1 << s)) == 0){continue;}for(int t = 0; t < K; ++t){if(bit & (1 << t)){continue;}int nbit = bit | (1 << t);int c = edges[R[t]][2];for(int x = 0; x < 2; ++x){for(int y = 0; y < 2; ++y){int p = edges[R[s]][x], q = edges[R[t]][y ^ 1];int d = dp[bit][s][x] + dist[p][q] + c;if(dp[nbit][t][y] <= d){continue;}dp[nbit][t][y] = d;}}}}}int ans = inf;for(int i = 0; i < K; ++i){for(int j = 0; j < 2; ++j){int d = dp[(1 << K) - 1][i][j] + dist[edges[R[i]][j]][N - 1];if(ans <= d){continue;}ans = d;}}cout << ans << endl;return 0;}