Submission #1082404

#TimeUsernameProblemLanguageResultExecution timeMemory
1082404dwuyCities (BOI16_cities)C++14
100 / 100
1987 ms50252 KiB
#include <bits/stdc++.h> #define MASK(x) (1LL<<(x)) using namespace std; typedef long long ll; const int MX = 100005; int n, k, m; int city[5]; ll f[MASK(5)][MX]; vector<pair<int, ll>> G[MX]; void nhap(){ cin >> n >> k >> m; for(int i=0; i<k; i++) cin >> city[i]; for(int i=1; i<=m; i++){ int u, v, c; cin >> u >> v >> c; G[u].push_back({v, c}); G[v].push_back({u, c}); } } void solve(){ memset(f, 0x3f, sizeof f); for(int mask=1; mask<MASK(k); mask++){ if(mask-(-mask&mask) == 0){ f[mask][city[__lg(mask)]] = 0; } else for(int Mask=mask; Mask>0; Mask=(Mask - 1)&mask){ for(int i=1; i<=n; i++){ f[mask][i] = min(f[mask][i], f[Mask][i] + f[mask^Mask][i]); } } priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> Q; for(int i=1; i<=n; i++) if(f[mask][i] != f[0][0]){ Q.push({0, i}); } while(Q.size()){ int u; ll du; tie(du, u) = Q.top(); Q.pop(); for(pair<int, ll> edge: G[u]){ int v; ll c; tie(v, c) = edge; if(f[mask][v] > f[mask][u] + c){ f[mask][v] = f[mask][u] + c; Q.push({f[mask][v], v}); } } } } ll ans = f[0][0]; for(int i=1; i<=n; i++) ans = min(ans, f[MASK(k)-1][i]); cout << ans; } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); nhap(); solve(); 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...