Submission #1111247

#TimeUsernameProblemLanguageResultExecution timeMemory
1111247f0rizenCities (BOI16_cities)C++17
100 / 100
1746 ms44792 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int inf = 1e9 + 7; const ll infll = 1e18; template<typename T> istream &operator>>(istream &is, vector<T> &a) { for (auto &i : a) { is >> i; } return is; } int32_t main() { #ifdef LOCAL freopen("/tmp/input.txt", "r", stdin); #else ios::sync_with_stdio(false); cin.tie(nullptr); #endif int n, k, m; cin >> n >> k >> m; vector<int> a(k); cin >> a; for (auto &i : a) { --i; } vector<vector<pair<int, int>>> g(n); for (int i = 0; i < m; ++i) { int u, v, w; cin >> u >> v >> w; --u, --v; g[u].push_back({v, w}); g[v].push_back({u, w}); } vector<vector<ll>> dp(1 << k, vector<ll>(n, infll)); for (int i = 0; i < k; ++i) { dp[1 << i][a[i]] = 0; } for (int mask = 0; mask < (1 << k); ++mask) { for (int s = mask; s > 0; s = (s - 1) & mask) { for (int i = 0; i < n; ++i) { dp[mask][i] = min(dp[mask][i], dp[s][i] + dp[mask ^ s][i]); } } using pii = pair<ll, int>; priority_queue<pii, vector<pii>, greater<pii>> pq; for (int i = 0; i < n; ++i) { if (dp[mask][i] < infll) { pq.push({dp[mask][i], i}); } } while (!pq.empty()) { auto [_, v] = pq.top(); pq.pop(); if (_ > dp[mask][v]) { continue; } for (auto [u, w] : g[v]) { if (dp[mask][u] > dp[mask][v] + w) { dp[mask][u] = dp[mask][v] + w; pq.push({dp[mask][u], u}); } } } } ll ans = infll; for (int i = 0; i < n; ++i) { ans = min(ans, dp[(1 << k) - 1][i]); } cout << ans << "\n"; return 0; }
#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...