Submission #394784

#	Time	Username	Problem	Language	Result	Execution time	Memory
394784		Nima_Naderi	Cities (BOI16_cities)	C++14	100 / 100	2667 ms	54596 KiB

cities

//In the name of God
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
const ll MXN = 1e5 + 10;
const ll MXK = 5;
const ll MXM = (1LL << 5) + 5;
const ll INF = 1e18;
ll n, m, k, ans;
ll Imp[MXK], dis[MXK][MXN], dp[MXM][MXN];
vector<pll> adj[MXN];
priority_queue<pll, vector<pll>, greater<pll>> pq;
bool vis[MXN], in[MXN];
void BFS(ll f, ll src){
	dis[f][src] = 0, pq.push({0, src});
	memset(vis, 0, sizeof vis);
	while(!pq.empty()){
		ll d, u; tie(d, u) = pq.top(); pq.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(auto Pr : adj[u]){
			ll v, w; tie(v, w) = Pr;
			if(!vis[v] && d + w < dis[f][v]){
				dis[f][v] = d + w;
				pq.push({dis[f][v], v});
			}
		}
	}
}
void Relax(ll f){
	memset(vis, 0, sizeof vis);
	for(int i = 1; i <= n; i ++) pq.push({dp[f][i], i});
	while(!pq.empty()){
		ll d, u; tie(d, u) = pq.top(); pq.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(auto Pr : adj[u]){
			ll v, w; tie(v, w) = Pr;
			if(!vis[v] && d + w < dp[f][v]){
				dp[f][v] = d + w;
				pq.push({dp[f][v], v});
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	cin >> n >> k >> m;
	memset(dis, 63, sizeof dis), memset(dp, 63, sizeof dp);
	for(int i = 0; i < k; i ++) cin >> Imp[i];
	for(int i = 0; i < m; i ++){
		ll u, v, w; cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	for(int i = 0; i < k; i ++) BFS(i, Imp[i]);
	for(int i = 0; i < k; i ++) dp[(1LL << i)][Imp[i]] = 0;
	for(int mask = 1; mask < (1LL << k); mask ++){
		for(int i = 1; i <= n; i ++){
			for(int sub = mask; sub; sub = (sub - 1) & mask){
				int oth = mask ^ sub;
				dp[mask][i] = min(dp[mask][i], dp[sub][i] + dp[oth][i]);
			}
		}
		Relax(mask);
	}
	cout << *min_element(dp[(1LL << k) - 1] + 1, dp[(1LL << k) - 1] + n + 1) << '\n';
	return 0;
}
//! N.N

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26