IOI2011 4번 CROCODILE

문제 링크

  • https://oj.uz/problem/view/IOI11_crocodile

문제 출처

  • 2011년 국제 정보 올림피아드 4번 (Day2 1번)

풀이

풀이는 1분 이내로 생각났고, 구현까지 16분 걸린 문제입니다.

0번 방에서 탈출구로 최대한 빠르게 이동해야 합니다. 간선에 음수가 없고, 최대한 빨리 이동을 해야 하므로 다익스트라가 떠오릅니다.
문지기가 최선을 다해 막는다는 것은, 가장 빠른 길을 차단한다는 것을 의미합니다. 그러므로 다익스트라 알고리즘을 약간 변형해서 두 번째로 빠른 길을 찾아주면 됩니다.

0번에서 탈출구로 이동하는 것이 아닌, 탈출구에서 0번으로 이동하는 것으로 생각을 하면 문제를 매우 쉽게 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include "crocodile.h"
#include <vector>
#include <queue>
#include <utility>
using namespace std;

typedef pair<int, int> p;
vector<p> g[101010];
priority_queue<p> pq;
int dist1[101010], dist2[101010];
int visit[101010];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	for(int i=0; i<=n; i++) dist1[i] = dist2[i] = 1e9+7;
	for(int i=0; i<m; i++){
		int s = R[i][0], e = R[i][1], w = L[i];
		g[s].push_back({e, w});
		g[e].push_back({s, w});
	}
	for(int i=0; i<k; i++){
		dist1[P[i]] = dist2[P[i]] = 0;
		pq.push({0, P[i]});
	}

	while(!pq.empty()){
		int now = pq.top().second, cost = -pq.top().first;
		pq.pop();
		if(visit[now]) continue;
		visit[now] = 1;

		for(auto i : g[now]){
			int nxt = i.first, nxtCost = i.second;
			if(visit[nxt]) continue;
			//first
			if(dist1[nxt] > dist2[now] + nxtCost){
				dist2[nxt] = dist1[nxt];
				dist1[nxt] = dist2[now] + nxtCost;
				if(dist2[nxt] < 1e9+7) pq.push({-dist2[nxt], nxt});
			}
			//second
			else if(dist2[nxt] > dist2[now] + nxtCost){
				dist2[nxt] = dist2[now] + nxtCost;
				pq.push({-dist2[nxt], nxt});
			}
		}
	}

	return dist2[0];
}