Submission #287842

#	Time	Username	Problem	Language	Result	Execution time	Memory
287842		nandonathaniel	Cities (BOI16_cities)	C++14	100 / 100	2998 ms	42524 KiB

cities

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef pair<long long,int> pli;
const long long INF=1e18;
const int MAXN=1e5+5,MAXK=5;
long long dist[1<<MAXK][MAXN];
vector<pii> adj[MAXN];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n,k,m,x,u,v,w;
	cin >> n >> k >> m;
	for(int i=1;i<=n;i++)dist[0][i]=0;
	for(int i=1;i<(1<<k);i++){
		for(int j=1;j<=n;j++)dist[i][j]=INF;
	}
	for(int i=0;i<k;i++){
		cin >> x;
		dist[1<<i][x]=0;
	}
	for(int i=1;i<=m;i++){
		cin >> u >> v >> w;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});	
	}
	priority_queue<pli,vector<pli>,greater<pli> > PQ;
	for(int i=1;i<(1<<k);i++){
		for(int j=(j-1)&i;j>0;j=(j-1)&i){  //iterate submask
			for(int l=1;l<=n;l++)dist[i][l]=min(dist[i][l],dist[j][l]+dist[i^j][l]);
		}
		for(int l=1;l<=n;l++){
			if(dist[i][l]<INF)PQ.push({dist[i][l],l});
		}
		while(!PQ.empty()){
			pii now=PQ.top();
			PQ.pop();
			if(dist[i][now.second]<now.first)continue;
			for(auto nxt : adj[now.second]){
				if(dist[i][nxt.first]>dist[i][now.second]+nxt.second){
					dist[i][nxt.first]=dist[i][now.second]+nxt.second;
					PQ.push({dist[i][nxt.first],nxt.first});
				}
			}
		}
	}
	long long ans=INF;
	for(int i=1;i<=n;i++)ans=min(ans,dist[(1<<k)-1][i]);
	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