Submission #946303

#TimeUsernameProblemLanguageResultExecution timeMemory
946303phoenix0423Cities (BOI16_cities)C++17
100 / 100
1802 ms51632 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; #define fastio ios::sync_with_stdio(false), cin.tie(0) #pragma GCC optimize("Ofast", "unroll-loops") #define pb push_back #define eb emplace_back #define f first #define s second #define int long long #define lowbit(x) x&-x const int maxn = 1e5 + 5; const int INF = 1e18; int dp[40][maxn]; int n, k, m; vector<pll> adj[maxn]; signed main(void){ fastio; cin>>n>>k>>m; vector<int> a(k); for(int i = 0; i < k; i++) cin>>a[i], a[i] --; for(int i = 0; i < m; i++){ int a, b, w; cin>>a>>b>>w; a--, b--; adj[a].eb(b, w); adj[b].eb(a, w); } for(int i = 1; i < (1 << k); i++){ for(int j = 0; j < n; j++) dp[i][j] = INF; } for(int i = 0; i < k; i++) dp[(1 << i)][a[i]] = 0; for(int mask = 0; mask < (1 << k); mask++){ for(int i = 0; i < n; i++){ for(int s = mask; s; s = (s - 1) & mask){ dp[mask][i] = min(dp[mask][i], dp[s][i] + dp[mask ^ s][i]); } } priority_queue<pll, vector<pll>, greater<pll>> q; for(int i = 0; i < n; i++) q.push({dp[mask][i], i}); while(!q.empty()){ auto [d, pos] = q.top(); q.pop(); if(dp[mask][pos] != d) continue; for(auto [x, w] : adj[pos]){ if(dp[mask][x] > d + w){ dp[mask][x] = d + w; q.push({dp[mask][x], x}); } } } } int ans = INF; for(int i = 0; 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...