結果
問題 | No.1812 Uribo Road |
ユーザー |
![]() |
提出日時 | 2024-09-09 01:21:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 103 ms / 5,000 ms |
コード長 | 2,830 bytes |
コンパイル時間 | 2,834 ms |
コンパイル使用メモリ | 223,352 KB |
最終ジャッジ日時 | 2025-02-24 06:11:10 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>#define int long long#define endl '\n'using namespace std;const int INF = 1e18;struct Edge {int u, d;};vector<vector<Edge>> gr(10001, vector<Edge>());vector<int> dijkstra(int start) {vector<int> dist(gr.size(), INF);dist[start] = 0;priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;q.push({0, start});while (!q.empty()) {int v = q.top().second, d = q.top().first;q.pop();if (dist[v] < d) continue;for (auto [u, d] : gr[v]) {if (dist[v] + d < dist[u]) {dist[u] = dist[v] + d;q.push({dist[u], u});}}}return dist;}int dist[30][1 << 12];struct Road {int v, u, d;};int solve() {int n, m; cin >> n >> m;int r; cin >> r;vector<int> vr;for (int i = 0; i < r; i++) {int c;cin >> c;c--;vr.push_back(c);}sort(vr.begin(), vr.end());vector<Road> main_r;for (int i = 0; i < m; i++) {int v, u, d; cin >> v >> u >> d;v--;u--;gr[v].push_back({u, d});gr[u].push_back({v, d});if (vr.size() && i == vr.front()) {main_r.push_back({v, u, d});vr.erase(vr.begin());}}set<int> s_main_c;for (int i = 0; i < r; i++) {s_main_c.insert(main_r[i].u);s_main_c.insert(main_r[i].v);}s_main_c.insert(0);s_main_c.insert(n - 1);vector<int> main_c(s_main_c.begin(), s_main_c.end());int k = main_c.size();int mat[k][k];map<int, int> mp;for (int i = 0; i < k; i++) {mp[main_c[i]] = i;vector<int> dist = dijkstra(main_c[i]);for (int j = 0; j < k; j++) {mat[i][j] = dist[main_c[j]];}}for (int i = 0; i < k; i++) {for (int j = 0; j < (1 << r); j++) {dist[i][j] = INF;}dist[i][0] = mat[0][i];}for (int s = 1; s < (1 << r); s++) {for (int i = 0; i < r; i++) {if (s & (1 << i)) {int v = mp[main_r[i].v], u = mp[main_r[i].u], d = main_r[i].d;dist[v][s] = min(dist[v][s], dist[u][s ^ (1 << i)] + d);dist[u][s] = min(dist[u][s], dist[v][s ^ (1 << i)] + d);for (int j = 0; j < k; j++) {dist[j][s] = min(dist[j][s], dist[v][s] + mat[v][j]);dist[j][s] = min(dist[j][s], dist[u][s] + mat[u][j]);}}}}cout << dist[k - 1][(1 << r) - 1] << endl;return 1;}int32_t main() {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);int t = 1;// cin >> t;while (t--) {solve();}return 0;}