Submission #255464

#	Time	Username	Problem	Language	Result	Execution time	Memory
255464		kshitij_sodani	Cities (BOI16_cities)	C++14	0 / 100	300 ms	184440 KiB

cities

//#pragma GCC optimize("Ofast,unroll-loops")


#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
llo n,k,m;
vector<pair<llo,llo>> adj[100001];
vector<llo> dd;
llo dist[5][100001];
void dj(llo tt,llo s){
	for(llo i=0;i<n;i++){
		dist[tt][i]=-1;
	}
	dist[tt][s]=0;
	priority_queue<pair<llo,llo>> ss;
	ss.push({0,s});
	while(ss.size()){
		pair<llo,llo> no=ss.top();
		ss.pop();
		for(auto j:adj[no.b]){
			if(dist[tt][j.a]==-1 or dist[tt][j.a]>dist[tt][no.b]+j.b){
				dist[tt][j.a]=dist[tt][no.b]+j.b;
				ss.push({-dist[tt][j.a],j.b});
			}
		}
	}
}
llo ans=0;
vector<pair<pair<llo,llo>,llo>> adj2[100001][32];
llo dist2[100001][32];
void dj2(llo s){
	for(llo i=0;i<n;i++){
		for(llo j=0;j<(1<<k);j++){
			dist2[i][j]=-1;
		}
	}
	dist2[s][0]=0;
	priority_queue<pair<llo,pair<llo,llo>>> ss;
	ss.push({0,{s,0}});
	while(ss.size()){
		pair<llo,pair<llo,llo>> no=ss.top();
		ss.pop();
		for(auto j:adj2[no.b.a][no.b.b]){
		//	cout<<j.a.a<<":"<<j.a.b<<":"<<j.b<<":"<<dist2[j.a.a][j.a.b]<<endl;
			if(dist2[j.a.a][j.a.b]==-1 or dist2[j.a.a][j.a.b]>dist2[no.b.a][no.b.b]+j.b){
				dist2[j.a.a][j.a.b]=dist2[no.b.a][no.b.b]+j.b;
				ss.push({-dist2[j.a.a][j.a.b],j.a});
			}
		}
	}
	for(auto j:dd){
		ans=min(ans,dist2[j][(1<<k)-1]);
	}
	/*cout<<endl;
	for(llo i=0;i<n;i++){
		for(llo j=0;j<(1<<k);j++){
			cout<<dist[i][j]<<",";
		}
		cout<<endl;
	}
	cout<<endl;*/
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k>>m;
	for(llo i=0;i<k;i++){
		llo aa;
		cin>>aa;
		aa--;
		dd.pb(aa);
	}
	for(llo i=0;i<m;i++){
		llo aa,bb,cc;
		cin>>aa>>bb>>cc;
		aa--;
		bb--;
		adj[aa].pb({bb,cc});
		adj[bb].pb({aa,cc});
		ans+=cc;
	}
	for(llo i=0;i<k;i++){
		dj(i,dd[i]);
	}
	/*for(llo i=0;i<k;i++){
		for(llo j=0;j<n;j++){
			cout<<dist[i][j]<<",";
		}
		cout<<endl;
	}*/
	for(llo i=0;i<n;i++){
		for(llo j=0;j<(1<<k);j++){
			for(llo kk=0;kk<k;kk++){
				if((1<<kk)&j){
					adj2[i][j-(1<<kk)].pb({{i,j},dist[kk][i]});
				}
			}
			for(auto kk:adj[i]){
				adj2[i][j].pb({{kk.a,j},kk.b});
			}
		}
	}
	for(llo i=0;i<k;i++){
		dj2(dd[i]);
	}
	cout<<ans<<endl;



	

























	return 0;
}

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