oj.uz

Submission #108293

# Submission time Handle Problem Language Result Execution time Memory
108293 2019-04-28T13:10:14 Z SecretAgent007 Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 2 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;
#include "crocodile.h"

//#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[]){
	
	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]));
	}
	
	priority_queue< pair<long long, long long>, vector< pair<long long, long long> >, greater< pair<long long, long long> > > pq;
	
	vector< long long > distToExit(n, INF);
	
	for(int i = 0; i < k; i++){
		pq.push(make_pair(0,p[i]));
		distToExit[p[i]] = 0;
	}
	
	while(!pq.empty()){
		pair<long long, long long> pa = pq.top();
		pq.pop();
		
		if(distToExit[pa.second] != pa.first) continue;
		
		for(auto a : Graph[pa.second]){
			if(distToExit[a.second] > pa.first+a.first){
				distToExit[a.second] = pa.first+a.first;
				pq.push(make_pair(distToExit[a.second], a.second));
			}
		}
	}
	
	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;
		
		int forget = 0;
		long long mini = INF;
		
		for(auto a : Graph[pa.second]){
			if(distToExit[a.second]+a.first < mini){
				mini = distToExit[a.second]+a.first;
				forget = a.second;
			}
		}
		
		for(auto a : Graph[pa.second]){
			
			if(forget == a.second) 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 2 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 2 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 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -