백준 11952 - 좀비(C++)

문제 링크입니다. https://www.acmicpc.net/problem/11952

11952번: 좀비

다른 목적을 가진 다익스트라를 2번 사용해 푸는 문제였습니다.

좀비가 점령한 도시가 있을 때, 다른 도시들을 거쳐 N번 도시로 갈 수 있는 최소 비용을 구하는 문제입니다.
점령된 도시와 거리가 S 이하인 도시는 숙박비를 q로, 아닌 도시는 p로 받습니다.

먼저, 도시들이 점령 당한 도시들로부터 얼마나 떨어져 있는지를 구해야 합니다.
여기서 주의할 점은 점령 당한 도시가 하나가 아닐 수도 있기에,  어떤 도시에서 시작하냐에 따라서 도시마다 거리가 다를 수 있습니다.
이를 방지하기 위해서 탐색을 돌릴 때, 점령당한 도시를 한꺼번에 넣어, 최소 거리를 구할 수 있도록 해야합니다.

도시들간의 최소 거라를 구했다면, 이를 바탕으로 1번에서 시작해 N번 도시까지 탐색을 돌려주면 됩니다.
점령당한 도시는 가면 안되며 X번 도시에서 숙박을 할 때,  거리에 따라서 숙박 비용을 다르게 해주시면 됩니다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <climits>
#define INF LLONG_MAX
#define F first
#define S second

using namespace std;

int N, M, K, S;
int p, q;
int danger[100001]; // 점령당한 도시로부터 얼마나 떨어져있는지
vector<int> connect[100001];
long long Distance[100001];
priority_queue<pair<long long, int>> Q;
 
void reset_distance(){
	for(int i = 1; i <= N; i++) Distance[i] = INF;
}

void Dijstra(int st){
	reset_distance();
	Distance[st] = 0;
	Q.push({-0, st});
	while(!Q.empty()){
		int x = Q.top().S;
		long long cost = -Q.top().F;
		Q.pop();
		if(Distance[x] < cost) continue;
		for(int i = 0; i < connect[x].size(); i++){
			int xx = connect[x][i];
			long long n_cost;
			if(danger[xx] == 0) continue;
			if(danger[xx] > S) n_cost = cost + p;
			else n_cost = cost + q;
			if(Distance[xx] > n_cost){
				Distance[xx] = n_cost;
				Q.push({-Distance[xx], xx});
			}
		}
	}
}

void find_danger(){
	while(!Q.empty()){
		int x = Q.top().S;
		int cost = -Q.top().F;
		Q.pop();
		if(danger[x] < cost) continue;
		for(int i = 0; i < connect[x].size(); i++){
			int xx = connect[x][i];
			int n_cost = cost + 1;
			if(danger[xx] > n_cost){
				danger[xx] = n_cost;
				Q.push({-danger[xx], xx});
			}
		}
	}
}

void solve(){
	find_danger();
	Dijstra(1);
	if(danger[N] > S) cout << Distance[N] - p;
	else cout << Distance[N] - q;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> K >> S;
	cin >> p >> q;
	for(int i = 1; i <= N; i++) danger[i] = 987654321;
	for(int i = 1; i <= K; i++) {
		int x;
		scanf("%d", &x);
		danger[x] = 0;
		Q.push({-0, x});
	}
	for(int i = 1; i <= M; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		connect[x].push_back(y);
		connect[y].push_back(x);
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.