Submission #734855

#TimeUsernameProblemLanguageResultExecution timeMemory
734855dong_liuCities (BOI16_cities)C++17
0 / 100
318 ms81012 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5, K = 5; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, k, m; cin >> n >> k >> m; static int v[K]; for (int i = 0; i < k; i++) cin >> v[i], v[i]--; static vector<pair<int, int>> g[N]; while (m--) { int i, j, w; cin >> i >> j >> w, i--, j--; g[i].push_back({j, w}), g[j].push_back({i, w}); } static long long d[K][N]; for (int s = 0; s < k; s++) { long long *t = d[s]; priority_queue<pair<long long, int>> q; memset(t, 0x3f, n * 8); q.push({-(t[v[s]] = 0), v[s]}); while (!q.empty()) { auto [x, i] = q.top(); x *= -1, q.pop(); if (t[i] != x) continue; for (auto [j, w] : g[i]) if (x + w < t[j]) q.push({-(t[j] = x + w), j}); } } static long long f[N][1 << K]; for (int i = 0; i < n; i++) memset(f[i], 0x3f, (1 << k) * 8); priority_queue<tuple<long long, int, int>> q; for (int i = 0; i < n; i++) q.push({-(f[i][1 << i] = 0), v[i], 1 << i}); while (!q.empty()) { auto [x, i, b] = q.top(); x *= -1; q.pop(); if (f[i][b] != x) continue; for (auto [j, w] : g[i]) if (x + w < f[j][b]) q.push({-(f[j][b] = x + w), j, b}); for (int s = 0; s < k; s++) if ((b >> s & 1) == 0 && x + d[s][i] < f[i][b | (1 << s)]) q.push({-(f[i][b | 1 << s] = x + d[s][i]), i, b | (1 << s)}); } long long ans = LLONG_MAX; for (int i = 0; i < n; i++) ans = min(ans, f[i][(1 << k) - 1]); cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...