Submission #693842

#	Time	Username	Problem	Language	Result	Execution time	Memory
693842		ajab_01	Cities (BOI16_cities)	C++17	100 / 100	3267 ms	72252 KiB

cities

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
const int K = 5;
long long INF;
vector<pair<int , int> > g[N];
vector<int> vec;
long long dp[N][1 << K] , ans;
int n , k , m;
bool vis[N];

void dij(int mask , int sit){
	priority_queue<pair<long long , int> > pq;
	for(int i = 1 ; i <= n ; i++)
		if(dp[i][mask] < INF)
			pq.push({-dp[i][mask] , i});
	while(!pq.empty()){
		int ver = pq.top().second;
		pq.pop();
		if(vis[ver]) continue;
		vis[ver] = 1;
		if(sit) ans = min(ans , dp[ver][mask]);
		for(auto i : g[ver]){
			int w = i.second , v = i.first;
			if(dp[v][mask] > dp[ver][mask] + w){
				dp[v][mask] = dp[ver][mask] + w;
				pq.push({-dp[v][mask] , v});
			}
		}
	}
	for(int i = 1 ; i <= n ; i++)
		vis[i] = 0;
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> k >> m;
	for(int i = 0 ; i < k ; i++){
		int x;
		cin >> x;
		vec.push_back(x);
	}
	for(int i = 0 ; i < m ; i++){
		int u , v , w;
		cin >> u >> v >> w;
		g[u].push_back({v , w});
		g[v].push_back({u , w});
	}

	memset(dp , 63 , sizeof(dp));

	ans = INF = dp[0][0];

	for(int i = 0 ; i < k ; i++){
		dp[vec[i]][1 << i] = 0;
		dij(1 << i , 0);
	}

	for(int mask = 3 ; mask < (1 << k) ; mask++){
		int cnt = 0;
		for(int i = 0 ; i < k ; i++)
			if(mask & (1 << i))
				cnt++;
		if(cnt == 1) continue;
		for(int v = 1 ; v <= n ; v++){
			for(auto j : g[v]){
				int u = j.first , w = j.second , sub = mask;
				while(sub){
					dp[v][mask] = min(dp[v][mask] , dp[v][sub] + dp[u][mask ^ sub] + w);
					sub--;
					sub &= mask;
				}
			}
		}
		dij(mask , (mask == (1 << k) - 1 ? 1 : 0));
	}
	cout << ans << '\n';
	return 0;
}

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