oj.uz

Submission #108261

# Submission time Handle Problem Language Result Execution time Memory
108261 2019-04-28T11:30:47 Z SecretAgent007 Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 3 ms 384 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -