백준 11952 좀비

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

11952번: 좀비

다익스트라와 그래프 탐색을 이용하여 푸는 문제였습니다.

문제에서 요구하는 1에서 N까지 드는 최단 비용은 다익스트라 알고리즘을 통해 구할 수 있습니다. 하지만 좀비가 점령한 도시라는 변수가 있습니다. 좀비가 점령한 도시로부터 S이하의 거리에 존재하는 도시들은 비용이 틀려지기 때문에 bfs 혹은 dfs와 같은 그래프 탐색으로 이러한 도시들을 구해야 합니다. 또한 길의 수가 최대 20만이고 비용이 최대 10만이므로 최단비용은 int범위를 넘게되므로 주의해야합니다.

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
int N,M,K,S;
long long p,q;
int zombie[100001];
int dist[100001];
long long dijk_dist[100001];
vector<vector<int>> E(100001,vector<int>());
void dfs(int now,int now_dist){
    zombie[now]=1;
    dist[now]=now_dist;
    if(now_dist==S) return;
    for(auto i : E[now]){
        if(now_dist+1<dist[i]) dfs(i,now_dist+1);
    }
}

void dijkstra(){
    for(int x=2;x<=N;x++) dijk_dist[x]=2e15;
    priority_queue<pair<long long,long long>> pq;
    pq.push({0,1});
    while(!pq.empty()){
        int now=pq.top().second;
        long long now_dist=-pq.top().first;
        pq.pop();
        if(dijk_dist[now]<now_dist) continue;
        for(auto i : E[now]){
            if(i==N){
                dijk_dist[i]=min(dijk_dist[i],now_dist);
                continue;
            }
            if(zombie[i]==0){
                if(dijk_dist[i]>now_dist+p){
                    dijk_dist[i]=now_dist+p;
                    pq.push({-now_dist-p,i});
                }
            }
            if(zombie[i]==1){
                if(dijk_dist[i]>now_dist+q){
                    dijk_dist[i]=now_dist+q;
                    pq.push({-now_dist-q,i});
                }
            }
        }
    }
}
int main(){
    cin>>N>>M>>K>>S>>p>>q;
    vector<int> zombie_city;
    for(int x=0;x<K;x++){
        int input;
        cin>>input;
        zombie_city.push_back(input);
    }
    for(int x=0;x<M;x++){
        int src,dst;
        cin>>src>>dst;
        E[src].push_back(dst);
        E[dst].push_back(src);
    }
    for(int x=0;x<=N;x++) dist[x]=2e9;
    for(auto i : zombie_city){
        dfs(i,0);
    }
    for(auto i : zombie_city){
        zombie[i]=2;
    }
    dijkstra();
    cout<<dijk_dist[N];
}