Submission #485525

#	Time	Username	Problem	Language	Result	Execution time	Memory
485525		minhcool	Cities (BOI16_cities)	C++17	100 / 100	4074 ms	54056 KiB

cities

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n, m, k;
 
int dp[N][32], nodes[N];
 
vector<ii> Adj[N];
 
vector<iii> edge;
 
void dijik(int msk){
	priority_queue<ii, vector<ii>, greater<ii>> pq;
	for(int i = 1; i <= n; i++) pq.push({dp[i][msk], i});
	//return;
	//int itr = 0;
	while(!pq.empty()){
		//itr++;
		int u = pq.top().se, d = pq.top().fi;
		//cout << u << "\n";
		//if(itr == 1) return;
		pq.pop();
		if(d != dp[u][msk]) continue;
		for(auto it : Adj[u]){
			int v = it.fi, w = it.se;
			if(dp[v][msk] <= dp[u][msk] + w) continue;
			dp[v][msk] = dp[u][msk] + w;
			pq.push({dp[v][msk], v});
		}
	}
}
 
void process(){
	cin >> n >> k >> m;
	for(int i = 0; i < k; i++) cin >> nodes[i];
	for(int i = 1; i <= m; i++){
		int x, y, w;
		cin >> x >> y >> w;
		Adj[x].pb({y, w});
		Adj[y].pb({x, w});
		edge.pb({{x, y}, w});
		edge.pb({{y, x}, w});
	}
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < (1ll << k); j++) dp[i][j] = oo;
	}
	for(int i = 0; i < k; i++){
		//for(int j = 1; j <= n; j++) dp[j][(1LL << i)] = oo;
		dp[nodes[i]][1LL << i] = 0;
		dijik(1LL << i);
	}
	//return;
	for(int i = 0; i < (1LL << k); i++){
		if(__builtin_popcountll(i) <= 1) continue;
		for(int sub = i - 1; sub; sub = (sub - 1) & i){
			for(auto it : edge){
				dp[it.fi.fi][i] = min(dp[it.fi.fi][i], dp[it.fi.fi][sub] + dp[it.fi.se][i ^ sub] + it.se);
			}
		}
      dijik(i);
	}/*
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < (1ll << k); j++) cout << i << " " << j << " " << dp[i][j] << "\n";
	}*/
	int mn = oo;
	for(int i = 1; i <= n; i++) mn = min(mn, dp[i][(1LL << k) - 1]);
	cout << mn;
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	process();
}

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