Submission #693868

#	Time	Username	Problem	Language	Result	Execution time	Memory
693868		amirhoseinfar1385	Cities (BOI16_cities)	C++17	100 / 100	3618 ms	52964 KiB

cities

#include<bits/stdc++.h>
using namespace std;
long long n,m,q;
const long long maxn=200000+5;
vector<long long>allq;
long long inf=1e16;
vector<pair<long long,long long>>adj[maxn];
vector<vector<long long>>dis;

void dij(long long u){
	priority_queue<pair<long long,long long>>st;
	for(long long j=1;j<=n;j++){
		st.push(make_pair(-dis[u][j],j));
	}
	//cout<<"what "<<u<<endl;
	vector<long long>vis(n+1);
	while((long long)st.size()>0){
		auto x=st.top();
		st.pop();
		if(vis[x.second]==1){
			continue;
		}
		vis[x.second]=1;
		dis[u][x.second]=-x.first;
		for(auto y:adj[x.second]){
			st.push(make_pair(-y.second+x.first,y.first));
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q>>m;
	allq.resize(q+1);
	dis.resize((1<<q),vector<long long>(n+1,inf));
	for(long long i=0;i<q;i++){
		cin>>allq[i];
	}
	for(long long i=0;i<m;i++){
		long long u,v,w;
		cin>>u>>v>>w;
		adj[u].push_back(make_pair(v,w));
		adj[v].push_back(make_pair(u,w));
	}
	for(long long i=1;i<=q;i++){
		for(long long j=1;j<(1<<q);j++){
			if(__builtin_popcount(j)!=i){
				continue;
			}
			for(long long h=1;h<=n;h++){
				for(long long z=j;z>0;z=(j&(z-1))){
					if(z==j){
						continue;
					}
					dis[j][h]=min(dis[j][h],dis[z][h]+dis[(j^z)][h]);
				}
			}
			if(i==1){
				int w=0,fj=j;
				while(fj%2==0){
					fj/=2;
					w++;
				}
				dis[j][allq[w]]=0;
			}
			//cout<<"salam"<<endl;
			dij(j);
		}
	}	
	long long res=inf;
	for(long long i=1;i<=n;i++){
		//cout<<i<<" "<<dis[(1<<q)-1][i]<<endl;
		res=min(res,dis[(1<<q)-1][i]);
	}
	cout<<res<<"\n";
}

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