oj.uz

Submission #287842

# Submission time Handle Problem Language Result Execution time Memory
287842 2020-09-01T04:13:01 Z nandonathaniel Cities (BOI16_cities) C++14
100 / 100
 2998 ms 42524 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 2816 KB Output is correct
5 Correct 2 ms 2816 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 713 ms 23836 KB Output is correct
2 Correct 614 ms 23260 KB Output is correct
3 Correct 411 ms 16528 KB Output is correct
4 Correct 75 ms 10872 KB Output is correct
5 Correct 342 ms 20456 KB Output is correct
6 Correct 70 ms 10744 KB Output is correct
7 Correct 5 ms 2944 KB Output is correct
8 Correct 4 ms 2944 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1400 ms 29932 KB Output is correct
2 Correct 1295 ms 29540 KB Output is correct
3 Correct 889 ms 22632 KB Output is correct
4 Correct 729 ms 21100 KB Output is correct
5 Correct 166 ms 13184 KB Output is correct
6 Correct 81 ms 12536 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2998 ms 42448 KB Output is correct
2 Correct 2946 ms 42524 KB Output is correct
3 Correct 2628 ms 42084 KB Output is correct
4 Correct 1958 ms 35180 KB Output is correct
5 Correct 1462 ms 27496 KB Output is correct
6 Correct 255 ms 14452 KB Output is correct
7 Correct 89 ms 12664 KB Output is correct