달빛 여우 16118

문제

접근 방법

다익스트라 응용문제라는 것은 눈치채기 쉽다.
하지만 그냥 응용해 주면 안 된다.

달빛 여우는 그냥 다익스트라를 적용해 줘도 달빛 늑대는 2배로 빠르게, 2배 느리게 경우를 반복해 줘야 한다.

그러한 점을 생각해 보면 d의 값은 홀수값을 허용하기에 2배로 하여서 사용해 주는 것이 좋다.

달빛 여우는 보통의 다익스트라를 적용해 준다.
달빛 늑대는 문제에서 요구하는 행동대로 다익스트라를 적용하면 된다. (2배 빠르게, 2배 느리게 반복)

하지만 거리를 기록하는 배열은 1차원으로 두면 안 된다.
2가지 상태가 존재하는 만큼 경유해서 가는 경우가 빠를 수 있기 때문이다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#define MAX_DIST 800000001
using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, bool> tiib;
vector<vector<pii>> graph;
vector<int> foxDist, wolfDist[2];
int N, M, a, b, d, cnt;
priority_queue<pii, vector<pii>, greater<pii>> foxPQ;
priority_queue<tiib, vector<tiib>, greater<tiib>> wolfPQ;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;
    graph = vector<vector<pii>>(N + 1, vector<pii>());
    foxDist = wolfDist[0] = wolfDist[1] = vector<int>(N + 1, MAX_DIST);
    while (M--)
    {
        cin >> a >> b >> d;
        d <<= 1;
        graph[a].push_back({d, b});
        graph[b].push_back({d, a});
    }
    foxPQ.push({0, 1});
    while (!foxPQ.empty())
    {
        pii cur = foxPQ.top();
        foxPQ.pop();
        if (foxDist[cur.second] != MAX_DIST)
            continue;
        foxDist[cur.second] = cur.first;
        for (pii next : graph[cur.second])
        {
            if (foxDist[next.second] <= next.first + cur.first)
                continue;
            foxPQ.push({next.first + cur.first, next.second});
        }
    }
    wolfPQ.push({0, 1, false});
    while (!wolfPQ.empty())
    {
        tiib cur = wolfPQ.top();
        wolfPQ.pop();
        int idx = get<1>(cur);
        int value = get<0>(cur);
        bool isRun = get<2>(cur);
        if (wolfDist[isRun][idx] != MAX_DIST)
            continue;
        wolfDist[isRun][idx] = value;
        for (pii next : graph[idx])
        {
            int nextValue = (isRun ? next.first << 1 : next.first >> 1) + value;
            if (wolfDist[!isRun][next.second] <= nextValue)
                continue;
            wolfPQ.push({nextValue, next.second, !isRun});
        }
    }
    for (int i = 2; i <= N; ++i)
        if (foxDist[i] < wolfDist[0][i] && foxDist[i] < wolfDist[1][i])
            ++cnt;
    cout << cnt;
    return 0;
}

풀이

여우의 거리와 2가지 상태를 저장한 늑대의 거리를 비교하여 여우의 값이 미만이면 개수를 증가시켜 주면 된다.