Submission #1093101

#TimeUsernameProblemLanguageResultExecution timeMemory
1093101juicyCities (BOI16_cities)C++17
100 / 100
4960 ms173440 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif int main() { ios::sync_with_stdio(false); cin.tie(nullptr); const long long inf = 1e18; int n, k, m; cin >> n >> k >> m; vector<int> city(k); for (int &u : city) { cin >> u; --u; } vector<vector<array<int, 2>>> g(n); while (m--) { int u, v, c; cin >> u >> v >> c; --u, --v; g[u].push_back({v, c}); g[v].push_back({u, c}); } vector d(n, vector<long long>(1 << k, inf)); using T = tuple<long long, int, int>; priority_queue<T, vector<T>, greater<T>> pq; for (int i = 0; i < k; ++i) { d[city[i]][1 << i] = 0; pq.push({0, city[i], 1 << i}); } while (pq.size()) { auto [c, u, m] = pq.top(); pq.pop(); if (c != d[u][m]) { continue; } for (auto [v, w] : g[u]) { if (d[v][m] > c + w) { pq.push({d[v][m] = c + w, v, m}); } } int mm = (1 << k) - 1 - m; for (int sm = mm; sm; sm = (sm - 1) & mm) { if (d[u][sm + m] > c + d[u][sm]) { pq.push({d[u][sm + m] = c + d[u][sm], u, sm + m}); } } } long long res = inf; for (int i = 0; i < n; ++i) { res = min(res, d[i].back()); } cout << res; 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...