백준5822 CROCODILE

작성일 | In

문제 링크

  • http://icpc.me/5822

문제 출처

  • 2011 IOI Day2 1번

풀이

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];
}