Submission #1245786

#TimeUsernameProblemLanguageResultExecution timeMemory
1245786BJoozzCities (BOI16_cities)C++20
0 / 100
6090 ms38676 KiB
#include <bits/stdc++.h> #define ii pair<int, int> #define fi first #define se second #define inf 0x3f3f3f3f3f3f3f3f using namespace std; using ll = long long; const ll mod=1e9+7; const int nx=1e5+5; int n, m, k, a[nx], id[nx]; vector<ii> adj[nx]; ll dp[nx][32], ans=inf; priority_queue<tuple<ll, int, int>> q; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>k>>m; memset(id, -1, sizeof(id)); for(int i = 0; i < k; i++) cin>>a[i], id[a[i]]=i; while(m--) { int u, v, w; cin>>u>>v>>w; adj[u].emplace_back(v, w); adj[v].emplace_back(u, w); } memset(dp, 0x3f, sizeof(dp)); for(int i = 1; i <= n; i++) { int mask=(id[i]==-1)?0:(1<<id[i]); dp[i][mask]=0; q.push({0, i, mask}); } while(q.size()) { ll dis; int u, mask; tie(dis, u, mask)=q.top(); if(mask==(1<<k)-1) break; q.pop(); if(dp[u][mask]!=dis) continue; for(auto it:adj[u]) { int nxt=mask|((id[it.fi]==-1)?0:(1<<id[it.fi])); if(dp[it.fi][nxt]>dp[u][mask]+it.se) dp[it.fi][nxt]=dp[u][mask]+it.se, q.push({dp[it.fi][nxt], it.fi, nxt}); } int rev=((1<<k)-1)^mask; for(int m1 = rev; m1 > 0; m1=(m1-1)&rev) { int nxt=mask|m1; if(dp[u][nxt]>dp[u][mask]+dp[u][m1]) dp[u][nxt]=dp[u][mask]+dp[u][m1], q.push({dp[u][nxt], u, nxt}); } } for(int i = 1; i <= n; i++) ans=min(ans, dp[i][(1<<k)-1]); 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...