[백준 16118번] 달빛 여우 (C++)

문제링크 : https://www.acmicpc.net/problem/16118

16118번: 달빛 여우

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int N, M, a, b, d, result = 0;

struct info
{
    int cost, node, state;
};

struct cmp{
    bool operator()(info &a, info &b){
        return a.cost > b.cost;
    }
};

int fox_dist[4001];
int wolf_dist[2][4001]; //걷기와 뛰기

vector<pii>edges[4001];

void dijkstra_fox()
{
    priority_queue<pii, vector<pii>, greater<pii>>pq; //가중치, 현재 위치
    pq.push({0, 1});

    fox_dist[1] = 0;

    while(!pq.empty())
    {
        int cur = pq.top().second; //현재 위치
        int cost = pq.top().first; //가중치 
        pq.pop();

        if(fox_dist[cur] < cost) continue;

        for(int i = 0; i<edges[cur].size(); i++)
        {
            int next = edges[cur][i].first; // 다음 위치
            int ncost = cost + edges[cur][i].second;

            if(fox_dist[next] > ncost)
            {
                fox_dist[next] = ncost;
                pq.push({ncost, next});
            }
        }
    }
}

void dijkstra_wolf()
{
    priority_queue<info, vector<info>, cmp> pq;
    pq.push({0, 1, 1}); //가중치, 위치, 상태

    wolf_dist[1][1] = 0;

    while(!pq.empty())
    {
        int cur = pq.top().node; //현재 위치
        int cost = pq.top().cost; //현재 가중치
        int state = pq.top().state; //변경예정 상태
        pq.pop();

        if(wolf_dist[state][cur] < cost) continue;

        for(int i=0; i<edges[cur].size(); i++)
        {
            int nstate = 1 - state;  //현재 상태
            int next = edges[cur][i].first;
            int ncost;
            if(state == 1) ncost = cost + edges[cur][i].second/2; //뛸 예정
            else ncost = cost + edges[cur][i].second*2; //걷을 예정

            if(wolf_dist[nstate][next] > ncost)
            {
                wolf_dist[nstate][next] = ncost;
                pq.push({ncost, next, nstate}); //다음 위치, 가중치, 변경예정 상태
            }
        }
    }
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;

    for(int i=1; i<=N; i++)
    {
        fox_dist[i]=MAX;
        wolf_dist[0][i]=MAX;
        wolf_dist[1][i]=MAX;
    }

    for(int i=0; i<M; i++)
    {
        cin >> a >> b >> d;  //a번, b번 가중치 d(오솔길)
        edges[a].push_back({b, d*2});
        edges[b].push_back({a, d*2});
    }

    dijkstra_fox();
    dijkstra_wolf();
    
    for(int i=2; i<=N; i++)
    {
        if(fox_dist[i] < min(wolf_dist[0][i], wolf_dist[1][i]))
        {
            result++;
        }
    }

    cout << result;
}

늑대의 경우 걷는 경우와 뛰는 경우 2가지가 있다.

이를 설정하는데 굉장히 헷갈렸다.

 

지금 현재 위치가 뛰는 것이 아니라 뛸 예정이기 때문에, 실제로 뛰는 상태는 다음 위치에서이다.

이를 주의하여 풀어야 한다.