Submission #391053

#TimeUsernameProblemLanguageResultExecution timeMemory
391053kostia244Cities (BOI16_cities)C++17
100 / 100
2676 ms46232 KiB
#pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx,avx2,sse,sse2") #include<bits/stdc++.h> using namespace std; using ll = long long; const int maxn = 1<<17; const ll inf = 1ll<<60; int n, k, m; ll dp[32][maxn]; vector<array<int, 2>> g[maxn]; ll z[maxn]; void fix_layer(int msk) { priority_queue<pair<ll, int>> pq; for(int i = 1; i <= n; i++) if((z[i] = dp[msk][i]) < inf) pq.push({-dp[msk][i], i}); while(!pq.empty()) { auto [di, v] = pq.top(); pq.pop();di *= -1; //cout << di << " _ " << v << endl; if(z[v] < di) continue; for(auto [x, y] : g[v]) { if(z[x] > di+y) { z[x] = di+y; pq.push({-(di+y), x}); } } } for(int i = 1; i <= n; i++) dp[msk][i] = z[i]; } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> k >> m; for(int j = 32; j--;) for(int i = 1; i <= n; i++) dp[j][i] = inf; for(int t, i = k; i--;) { cin >> t; dp[(1<<i)][t] = 0; } for(int f, t, c, i = 0; i < m; i++) { cin >> f >> t >> c; g[f].push_back({t, c}); g[t].push_back({f, c}); } for(int msk = 0; msk < 32; msk++) { for(int j = msk; j; j = msk&(j-1)) for(int v = 1; v <= n; v++) dp[msk][v] = min(dp[msk][v], dp[msk^j][v] + dp[j][v]); fix_layer(msk); } ll ans = inf; for(int i = 1; i <= n; i++) ans = min(ans, dp[(1<<k)-1][i]); 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...