oj.uz

Submission #693868

# Submission time Handle Problem Language Result Execution time Memory
693868 2023-02-03T10:49:25 Z amirhoseinfar1385 Cities (BOI16_cities) C++17
100 / 100
 3618 ms 52964 KB 
#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.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 937 ms 34008 KB Output is correct
2 Correct 896 ms 33556 KB Output is correct
3 Correct 377 ms 20348 KB Output is correct
4 Correct 567 ms 28340 KB Output is correct
5 Correct 440 ms 30864 KB Output is correct
6 Correct 271 ms 28300 KB Output is correct
7 Correct 7 ms 5204 KB Output is correct
8 Correct 5 ms 5204 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5364 KB Output is correct
2 Correct 10 ms 5332 KB Output is correct
3 Correct 7 ms 5204 KB Output is correct
4 Correct 10 ms 5204 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1718 ms 40360 KB Output is correct
2 Correct 1757 ms 39680 KB Output is correct
3 Correct 872 ms 26832 KB Output is correct
4 Correct 1484 ms 34712 KB Output is correct
5 Correct 1215 ms 28956 KB Output is correct
6 Correct 1159 ms 31148 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3618 ms 52916 KB Output is correct
2 Correct 3494 ms 52964 KB Output is correct
3 Correct 3526 ms 52360 KB Output is correct
4 Correct 1653 ms 39312 KB Output is correct
5 Correct 3037 ms 41120 KB Output is correct
6 Correct 2419 ms 30432 KB Output is correct
7 Correct 2299 ms 31220 KB Output is correct