Submission #108261

#	Time	Username	Problem	Language	Result	Execution time	Memory
108261		SecretAgent007	Crocodile's Underground City (IOI11_crocodile)	C++17	0 / 100	3 ms	384 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;

//#define int long long 

const long long INF = 1e18;

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
	
	set< int > exit;
	
	for(int i = 0; i < k; i++){
		exit.insert(p[i]);
	}
	
	vector< vector< pair<long long, long long> > > Graph(n);
	
	for(int i = 0; i < m; i++){
		Graph[r[i][0]].push_back(make_pair(l[i], r[i][1]));
		Graph[r[i][1]].push_back(make_pair(l[i], r[i][0]));
	}
	
	for(int i = 0; i < n; i++){
		sort(Graph[i].begin(), Graph[i].end());
	}
	
	priority_queue< pair<long long, long long>, vector< pair<long long, long long> >, greater< pair<long long, long long> > > pq;
	
	vector< long long > dist(n, INF);
	
	dist[0] = 0;
	pq.push(make_pair(0,0));
	
	long long ans = INF;
	
	while(!pq.empty()){
		
		pair<int, int> pa = pq.top();
		pq.pop();
		
		if(dist[pa.second] != pa.first) continue;
		
		bool verif = false;
		
		for(auto a : Graph[pa.second]){
			
			if(!verif && exit.count(a.second)){
				verif = true;
				continue;
			}
			
			if(dist[a.second] > a.first+pa.first){
				dist[a.second] = a.first+pa.first;
				pq.push(make_pair(dist[a.second],a.second));
			}
			
		}
		
	}
	
	for(int i = 0; i < k; i++){
		ans = min(ans, dist[p[i]]);
	}
	
	return ans;
} 
/*
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m, k;
	cin >> n >> m >> k;
	
	int r[m][2];
	int l[m];
	int p[k];
	
	for(int i = 0; i < m; i++){
		cin >> r[i][0] >> r[i][1];
	}
	for(int i = 0; i < m; i++){
		cin >> l[i];
	}
	for(int i = 0; i < k; i++){
		cin >> p[i];
	}
	
	cout << travel_plan(n,m,r,l,k,p) << endl;
}
*/

• Subtask 1: 0 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11