oj.uz

Submission #255496

# Submission time Handle Problem Language Result Execution time Memory
255496 2020-08-01T06:27:21 Z kshitij_sodani Cities (BOI16_cities) C++14
100 / 100
 4679 ms 108024 KB 
//#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
int n,k,m;
vector<pair<int,int>> adj[100001];
vector<int> dd;
llo dist[5][100001];
void dj(int tt,int s){
	for(llo i=0;i<n;i++){
		dist[tt][i]=-1;
	}
	dist[tt][s]=0;
	priority_queue<pair<llo,int>> ss;
	ss.push({0,s});
	/*	for(llo i=0;i<k;i++){
		for(llo j=0;j<n;j++){
			cout<<dist[i][j]<<",";
		}
		cout<<endl;
	}*/
	while(ss.size()){
		pair<llo,int> no=ss.top();
		ss.pop();
		if(-no.a>dist[tt][no.b]){
			continue;
		}
	//	cout<<no.a<<','<<no.b<<endl;
		for(auto j:adj[no.b]){
		//	cout<<j.a<<"::"<<j.b<<endl;

			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.a});
			}
		}
	}
}
llo ans=0;
//vector<pair<pair<int,int>,llo>> adj2[100001][32];
llo dist2[100001][32];
vector<int>kc[32];
void dj2(int 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<int,int>>> ss;
	ss.push({0,{s,0}});

	while(ss.size()){
		pair<llo,pair<int,int>> no=ss.top();
		ss.pop();
		if(-no.a>dist2[no.b.a][no.b.b]){
			continue;
		}
		for(auto j:adj[no.b.a]){
			if(dist2[j.a][no.b.b]==-1 or dist2[j.a][no.b.b]>dist2[no.b.a][no.b.b]+j.b){
				dist2[j.a][no.b.b]=dist2[no.b.a][no.b.b]+j.b;
				ss.push({-dist2[j.a][no.b.b],{j.a,no.b.b}});
			}
		}
		for(auto kk:kc[no.b.b]){
		//	if(((1<<kk)&no.b.b)==0){
				if(dist2[no.b.a][no.b.b+(1<<kk)]==-1 or dist2[no.b.a][no.b.b+(1<<kk)]>dist2[no.b.a][no.b.b]+dist[kk][no.b.a]){
					dist2[no.b.a][no.b.b+(1<<kk)]=dist2[no.b.a][no.b.b]+dist[kk][no.b.a];
					ss.push({-dist2[no.b.a][no.b.b+(1<<kk)],{no.b.a,no.b.b+(1<<kk)}});
				}	
		//	}
		}

		/*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(int i=0;i<k;i++){
		int aa;
		cin>>aa;
		aa--;
		dd.pb(aa);
	}
	for(int i=0;i<m;i++){
		int aa,bb,cc;
		cin>>aa>>bb>>cc;
		aa--;
		bb--;
		adj[aa].pb({bb,cc});
		adj[bb].pb({aa,cc});
		ans+=cc;
	}

	for(int i=0;i<k;i++){
		dj(i,dd[i]);
	}
	for(int i=0;i<(1<<k);i++){
		for(int j=0;j<k;j++){
			if(((1<<j)&i)==0){
				kc[i].pb(j);
			}
		}
	}

/*	for(int i=0;i<n;i++){
		for(int j=0;j<(1<<k);j++){
			for(int 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(int i=0;i<1;i++){
		dj2(dd[i]);
	}
	cout<<ans<<endl;


	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 992 ms 53116 KB Output is correct
2 Correct 980 ms 52404 KB Output is correct
3 Correct 580 ms 41692 KB Output is correct
4 Correct 87 ms 8104 KB Output is correct
5 Correct 503 ms 43928 KB Output is correct
6 Correct 80 ms 7780 KB Output is correct
7 Correct 7 ms 3328 KB Output is correct
8 Correct 4 ms 3200 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3456 KB Output is correct
2 Correct 9 ms 3456 KB Output is correct
3 Correct 7 ms 3208 KB Output is correct
4 Correct 7 ms 3200 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2104 ms 70248 KB Output is correct
2 Correct 1825 ms 73980 KB Output is correct
3 Correct 1424 ms 69252 KB Output is correct
4 Correct 1089 ms 43300 KB Output is correct
5 Correct 297 ms 22380 KB Output is correct
6 Correct 96 ms 13044 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4588 ms 103768 KB Output is correct
2 Correct 4679 ms 108024 KB Output is correct
3 Correct 4301 ms 107812 KB Output is correct
4 Correct 3064 ms 102908 KB Output is correct
5 Correct 2353 ms 60176 KB Output is correct
6 Correct 509 ms 22500 KB Output is correct
7 Correct 127 ms 13680 KB Output is correct