oj.uz

답안 #108306

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
108306 2019-04-28T13:34:34 Z SecretAgent007 악어의 지하 도시 (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[]){
	
	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< vector< long long > > dist(n, vector<long long>(2, INF));
	
	for(int i = 0; i < k; i++){
		dist[p[i]][0] = dist[p[i]][1] = 0;
		pq.push(make_pair(0,p[i]));
	}
	
	while(!pq.empty()){
		pair<long long, long long> pa = pq.top();
		pq.pop();
		
		long long cost = pa.first;
		int node = pa.second;
		
		for(auto a : Graph[node]){
		
			if(dist[a.second][0] > a.first + cost){
				dist[a.second][1] = dist[a.second][0];
				dist[a.second][0] = a.first+cost;
				pq.push(make_pair(dist[a.second][1], a.second)); 
			}else if(dist[a.second][1] > a.first+cost){
				dist[a.second][1] = a.first+cost;
				pq.push(make_pair(dist[a.second][1], a.second));
			}
		
		}
		
	}
	
	return dist[0][1];
}

Subtask #1
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Incorrect 3 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Incorrect 3 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Incorrect 3 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -