[BOJ/Gold 2] 백준 11952 좀비(C++)

문제 링크

https://www.acmicpc.net/problem/11952

11952번: 좀비

문제

JOI국은 N개의 도시와 M개의 도로로 이루어져 있다. 모든 도시는 도로로 연결되어 있으며, 각 도로를 통하지 않고는 다른 도시로 갈 수 없다.

이번에 K개의 도시는 좀비에 의해서 점령당했다. ㅠㅠ

따라서 경곽이는 벙커가 있는 가장 안전한 도시로 피난을 가기로 했다. 경곽이는 현재 1번 도시에 살고 있으며, 벙커가 있는 가장 안전한 피난처는 N번 도시이다. 1번 도시와 N번 도시는 아직 좀비에게 점령당하지 않았다.

경곽이는 각 도시를 이동할 때마다 1박을 해야하고, 1박을 할 때 숙박비를 지불해야 한다. 만약 그 도시가 좀비에게 점령당했다면 숙박이 불가능하다.

좀비에게 점령당한 도시로 부터 S번 이하의 이동으로 이동할 수 있는 모든 도시는 위험한 도시로 정의하며, 그 이외의 도시는 안전한 도시로 정의할 때, 만약 그 도시가 안전한 도시라면 숙박비가 p원이고, 만약 그 도시가 위험한 도시라면 숙박비는 q원이다. (좀비로부터 보호받기 위한 특별한 시큐리티 서비스를 제공하기 때문에 좀 더 비싸다 ㅠㅠ)

경곽이가 도시 1부터 N으로 이동하는 데 드는 최단 비용을 구하자.

입력

첫 번째 줄에 N, M, K, S가 공백으로 구분되어 입력된다. 각 값은 도시의 수, 길의 수, 좀비에게 점령당한 도시의 수, 위험한 도시의 범위 를 의미한다. (2 ≦ N ≦ 100000, 1 ≦ M ≦ 200000, 0 ≦ K ≦ N - 2, 0 ≦ S ≦ 100000)

다음 줄에는 숙박비를 나타내는 정수 p, q가 입력된다. (1 ≦ p ＜ q ≦ 100000)

그 다음 줄부터 K줄에 걸쳐서 좀비에게 점령당한 도시가 한 줄에 하나씩 주어진다.

다음 줄부터 M줄에 걸쳐서 각 도시를 연결하는 도로의 정보가 주어진다. 이 도로는 서로 양방향으로 이동 가능하다.

1번 도시에서 N번 도시로 항상 도달 가능하다.

출력

최소 비용을 출력한다.

예제 입력 1

13 21 1 1
1000 6000
7
1 2
3 7
2 4
5 8
8 9
2 5
3 4
4 7
9 10
10 11
5 9
7 12
3 6
4 5
1 3
11 12
6 7
8 11
6 13
7 8
12 13

예제 출력 1

11000

예제 입력 2

21 26 2 2
1000 2000
5
16
1 2
1 3
1 10
2 5
3 4
4 6
5 8
6 7
7 9
8 10
9 10
9 11
11 13
12 13
12 15
13 14
13 16
14 17
15 16
15 18
16 17
16 19
17 20
18 19
19 20
19 21

예제 출력 2

15000

힌트

도시는 이렇게 생겼다. 이때

1 - 2 - 5 - 9 - 10 - 11 - 12 - 13

으로 이동하는 것이 가장 싼 가격으로 이동할 수 있는 방법이다.

이때 1과 13에서는 숙박할 필요가 없다.

알고리즘 분류

• 그래프 탐색
• 최단 거리 알고리즘

풀이

우선 모든 도시의 숙박 비용을 P로 만들고, 좀비에게 점령된 도시의 숙박 비용은 0으로 설정한다.

BFS를 사용해서 좀비에게 점령된 도시들로부터 S 거리 이내에 있는 모든 도시의 숙박 비용을 Q로 설정한다.

그리고 다익스트라 알고리즘을 사용해서 1번 도시에서 각 도시까지 가는 데 드는 최소의 비용을 구하고

마지막으로 1에서 N까지 가는 데 드는 최소의 숙박 비용에서 N번 도시에서의 숙박 비용을 뺀 값을 출력한다. (N번 도시에서는 숙박하지 않으므로)

여기서 주의할 점은 숙박 비용이 정수 값을 넘어갈 수 있으므로 long long 자료형을 사용한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100005
#define LL long long
#define INF 2e9

using namespace std;
int N, M, K, S;
LL P, Q;
bool Zombie[MAX];
bool visited[MAX];
LL Cost[MAX];
LL DP[MAX];
vector<int> Vec[MAX];

void init() {
	for (int i = 1; i <= N; i++) {
		visited[i] = false;
		DP[i] = LLONG_MAX;
	}
}

void BFS(int X) {
	init();
	queue<pair<int, LL> > Que;
	visited[X] = true;
	Cost[X] = 0;
	Que.push(make_pair(X, 0));

	while (!Que.empty()) {
		int CurX = Que.front().first;
		LL CurS = Que.front().second;
		Que.pop();

		for (int i = 0; i < Vec[CurX].size(); i++) {
			int nextX = Vec[CurX][i];
			if (!visited[nextX] && (CurS + 1 <= S) && (!Zombie[nextX])) {
				visited[nextX] = true;
				Cost[nextX] = Q;
				Que.push(make_pair(nextX, CurS + 1));
			}
		}
	};
}

void Dijkstra() {
	priority_queue<pair<LL, int> > PQ;
	DP[1] = 0;
	PQ.push(make_pair(0, 1));

	while (!PQ.empty()) {
		LL CurCost = -PQ.top().first;
		int CurX = PQ.top().second;
		PQ.pop();

		for (int i = 0; i < Vec[CurX].size(); i++) {
			int nextX = Vec[CurX][i];
			if (Zombie[nextX]) {
				continue;
			}
			LL nextCost = CurCost + Cost[nextX];
			if (nextCost < DP[nextX]) {
				DP[nextX] = nextCost;
				PQ.push(make_pair(-nextCost, nextX));
			}
		}
	};
}

int main() {
	FIRST
	cin >> N >> M >> K >> S;
	cin >> P >> Q;
	for (int i = 1; i <= N; i++) {
		Cost[i] = P;
	}
	for (int i = 0; i < K; i++) {
		int X;
		cin >> X;
		Zombie[X] = true;
	}
	for (int i = 0; i < M; i++) {
		int X, Y;
		cin >> X >> Y;
		Vec[X].push_back(Y);
		Vec[Y].push_back(X);
	}
	for (int i = 1; i <= N; i++) {
		if (Zombie[i]) {
			BFS(i);
		}
	}
	Dijkstra();
	cout << DP[N] - Cost[N] << "\n";

	return 0;
}