Submission #1007742

#TimeUsernameProblemLanguageResultExecution timeMemory
1007742NintsiChkhaidzeCities (BOI16_cities)C++17
100 / 100
2141 ms156676 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define s second #define f first #define pii pair <int,int> #define left h*2,l,(l + r)/2 #define right h*2+1,(l + r)/2 + 1,r using namespace std; const int N = 2e5 + 5; const ll inf = 1e18; int arr[N]; ll dist[7][N],dd[34][N],ddd[N]; ll DD[34][N],val[34][N]; vector <pair <int,ll>> v[N]; signed main (){ ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL); int n,k,m; cin>>n>>k>>m; for (int i = 1; i <= k; i++) cin >> arr[i]; for (int i =1; i <= m; i++){ int a,b; ll c; cin>>a>>b>>c; v[a].pb({b,c}); v[b].pb({a,c}); } for (int i = 1; i <= k; i++){ for (int j = 1; j <= n; j++) dist[i][j] = inf; priority_queue<pair <ll,int>> pq; dist[i][arr[i]] = 0; pq.push({0,arr[i]}); while (pq.size()){ ll D = -pq.top().f; int x = pq.top().s; pq.pop(); if (dist[i][x] != D) continue; for (auto [to,w]: v[x]){ if (dist[i][to] > D + w){ dist[i][to] = D + w; pq.push({-dist[i][to],to}); } } } } ll ans=inf; for (int i = 1; i <= n; i++){ ll cur=0; for (int j = 1; j <= k; j++) cur += dist[j][i]; ans=min(ans,cur); } if (k < 4){ cout<<ans<<endl; exit(0); } for (int mask1=0;mask1<(1<<k); mask1++) for(int i=1;i<=n;i++) DD[mask1][i] = inf; for (int mask2=0;mask2<(1<<k); mask2++) for (int i = 1; i <= n; i++) for (int j=0;j<k;j++) if (((mask2>>j) & 1)) val[mask2][i] += (dist[j + 1][i]); for (int mask1 = 0; mask1 < (1<<k); mask1++){ priority_queue <pair <ll,int>> pq; for (int i = 1; i <= n; i++){ dd[mask1][i] = val[mask1][i]; pq.push({-dd[mask1][i],i}); } while (pq.size()){ ll D = -pq.top().f; int x = pq.top().s; pq.pop(); if (dd[mask1][x] != D) continue; for (auto [to,w]: v[x]){ if (dd[mask1][to] > D + w){ dd[mask1][to] = D + w; pq.push({-dd[mask1][to],to}); } } } for (int mask2 = 0; mask2 < (1<<k); mask2++){ int y = (mask1 & mask2); if (y > 0) continue; for (int i = 1; i <= n; i++){ ll kk = dd[mask1][i] + val[mask2][i]; DD[(mask1 | mask2)][i] = min(DD[(mask1 | mask2)][i],kk); } } } for (int mask1=0;mask1<(1<<k); mask1++){ priority_queue <pair <ll,int>> pq; for (int i = 1; i <= n; i++) ddd[i] = DD[mask1][i],pq.push({-ddd[i],i}); while (pq.size()){ ll D = -pq.top().f; int x = pq.top().s; pq.pop(); if (ddd[x] != D) continue; for (auto [to,w]: v[x]){ if (ddd[to] > D + w){ ddd[to] = D + w; pq.push({-ddd[to],to}); } } } for (int i = 1; i <= n; i++){ ddd[i] += (val[(((1<<k) - 1) ^ mask1)][i]); ans=min(ans,ddd[i]); } } cout<<ans; }
#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...