Submission #709940

#TimeUsernameProblemLanguageResultExecution timeMemory
709940noeditCities (BOI16_cities)C++17
100 / 100
5021 ms44384 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") using namespace std; const int INF = 1e9; typedef long long ll; const ll INFLL = 1e18; const int MAXN = 2e5; const int MAXK = 5; const int MAXMSK = 32; ll dp[MAXMSK][MAXN]; vector<vector<pair<int, int> > > g; signed main() { //ifstream cin("input.txt"); //ofstream cout("output.txt"); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, k, m; cin >> n >> k >> m; g.resize(n); vector<int> a(k); for (int i = 0; i < k; i++) cin >> a[i]; for (int i = 0; i < m; i++) { int x, y, z; cin >> x >> y >> z; x--; y--; g[x].push_back({y, z}); g[y].push_back({x, z}); } for (int i = 0; i < MAXMSK; i++) for (int j = 0; j < n; j++) dp[i][j] = INFLL; for (int i = 0; i < k; i++) { dp[1 << i][a[i] - 1] = 0; } for (int mask = 1; mask < (1 << k); mask++) { for (int sub1 = mask; sub1; sub1 = (sub1 - 1) & mask) { int sub2 = mask ^ sub1; for (int v = 0; v < n; v++) dp[mask][v] = min(dp[mask][v], dp[sub1][v] + dp[sub2][v]); } set<pair<ll, int> > st; for (int v = 0; v < n; v++) { if (dp[mask][v] == INFLL) continue; st.insert({dp[mask][v], v}); } while (!st.empty()) { auto [d, v] = *st.begin(); st.erase(st.begin()); for (auto&[u, w] : g[v]) { if (dp[mask][u] > d + w) { st.erase({dp[mask][u], u}); dp[mask][u] = d + w; st.insert({dp[mask][u], u}); } } } } ll ans = INFLL; // for (int i = 0; i < (1 << k); i++){ // cout << i << endl; // for (int j = 0; j < n; j++) // cout << dp[i][j] << " "; // cout << endl; // } for (int i = 0; i < n; i++) { ans = min(ans, dp[(1 << k) - 1][i]); } cout << ans; return 0; } /* 4 3 6 1 3 4 1 2 4 1 3 9 1 4 6 2 3 2 2 4 5 3 4 8 */
#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...