[baekjoon] 16118

달빛 여우 

문제

관악산 기슭에는 보름달을 기다리는 달빛 여우가 한 마리 살고 있다. 달빛 여우가 보름달의 달빛을 받으면 아름다운 구미호로 변신할 수 있다. 하지만 보름달을 기다리는 건 달빛 여우뿐만이 아니다. 달빛을 받아서 멋진 늑대인간이 되고 싶어 하는 달빛 늑대도 한 마리 살고 있다.

관악산에는 1번부터 N번까지의 번호가 붙은 N개의 나무 그루터기가 있고, 그루터기들 사이에는 M개의 오솔길이 나 있다. 오솔길은 어떤 방향으로든 지나갈 수 있으며, 어떤 두 그루터기 사이에 두 개 이상의 오솔길이 나 있는 경우는 없다. 달빛 여우와 달빛 늑대는 1번 나무 그루터기에서 살고 있다.

보름달이 뜨면 나무 그루터기들 중 하나가 달빛을 받아 밝게 빛나게 된다. 그러면 달빛 여우와 달빛 늑대는 먼저 달빛을 독차지하기 위해 최대한 빨리 오솔길을 따라서 그 그루터기로 달려가야 한다. 이때 달빛 여우는 늘 일정한 속도로 달려가는 반면, 달빛 늑대는 달빛 여우보다 더 빠르게 달릴 수 있지만 체력이 부족하기 때문에 다른 전략을 사용한다. 달빛 늑대는 출발할 때 오솔길 하나를 달빛 여우의 두 배의 속도로 달려가고, 그 뒤로는 오솔길 하나를 달빛 여우의 절반의 속도로 걸어가며 체력을 회복하고 나서 다음 오솔길을 다시 달빛 여우의 두 배의 속도로 달려가는 것을 반복한다. 달빛 여우와 달빛 늑대는 각자 가장 빠르게 달빛이 비치는 그루터기까지 다다를 수 있는 경로로 이동한다. 따라서 둘의 이동 경로가 서로 다를 수도 있다.

출제자는 관악산의 모든 동물을 사랑하지만, 이번에는 달빛 여우를 조금 더 사랑해 주기로 했다. 그래서 달빛 여우가 달빛 늑대보다 먼저 도착할 수 있는 그루터기에 달빛을 비춰 주려고 한다. 이런 그루터기가 몇 개나 있는지 알아보자.

입력

첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다.

두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b, 1 ≤ d ≤ 100,000)가 주어진다. 이는 a번 그루터기와 b번 그루터기 사이에 길이가 d인 오솔길이 나 있음을 의미한다.

출력

첫 줄에 달빛 여우가 달빛 늑대보다 먼저 도착할 수 있는 나무 그루터기의 개수를 출력한다.

예제 입력 

5 6
1 2 3
1 3 2
2 3 2
2 4 4
3 5 4
4 5 3

예제 출력

1

5번 그루터기에 달빛을 비추면 달빛 여우가 달빛 늑대보다 먼저 도착할 수 있다. 4번 그루터기에 달빛을 비추면 달빛 여우와 달빛 늑대가 동시에 도착한다.

풀이

여우의 경우에는 단순한 다익스트라로 최단거리를 구하면 되지만 늑대 녀석이 문제다.

늑대는 속도 2배, 1/2배, 2배, 1/2배를 반복하며 움직인다.

일단 아이디어는 큐에 다음 노드를 넣을 때 빠르게 가는지, 느리게 가는지를 판단하는 변수를 같이 넣어주는 것이었다.

 

그리고 여우의 경우는 한 가지의 결과만 저장하면 되지만 늑대는 2개의 결과를 저장해야 한다.

예를 들어 2번 노드에 대한 거리를 저장할 때 느리게 간경우 빠르게 간 경우 두 가지를 저장해줘야 한다.

또한 늑대가 1->2->3->1->2 이런 식으로 돌아가는 경우도 있을 수 있다. 즉 처음에 여우에서처럼 시작지점의 거리를 0으로 초기화하면 안 된다.

 

(무조건 되리라 생각했지만 거리를 계산할 때 실수형으로 계산해서 왜 안되지 하면서 삽질 엄청했다 ㅠㅠ)

 

#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

vector<pair<int, int>> *node; // <거리 , 노드>
long long *foxResult, **wolfResult;
long long INF = 0x7fffffffffffffff;

int stump, path; // 그루터기 수, 오솔길 수


void foxDijkstra(int start){
    for(int i = 0; i < stump+1; i++)foxResult[i] = INF;
    foxResult[start] = 0;
    priority_queue<pair<long long, int>> pq; // dis , node
    pq.push(make_pair(0, start));
    
    while(!pq.empty())
    {
        int currentNode = pq.top().second;
        long long currentDistance = -pq.top().first;
        pq.pop();
        
        if(currentDistance > foxResult[currentNode])continue;

        for(int i = 0; i < node[currentNode].size(); i++){
            int next = node[currentNode][i].second;
            long long nextDistance = node[currentNode][i].first + currentDistance;

            if(nextDistance < foxResult[next]){
                foxResult[next] = nextDistance;
                pq.push(make_pair(-nextDistance, next));
            }
        }
    }
}

void wolfDijkstra(int start){
    const int fast = 0;
    const int slow = 1;
    priority_queue<pair<pair<long long, int>, int>> pq; // <dis , node>, turn

    for(int i = 0; i < stump+1; i++){
        wolfResult[fast][i] = INF;
        wolfResult[slow][i] = INF;
    }
    
    
    pq.push(make_pair(make_pair(0, start), fast));
    
    while(!pq.empty())
    {
        int currentNode = pq.top().first.second;
        long long currentDistance = -pq.top().first.first;
        int turn = pq.top().second;

        pq.pop();
        
        if(currentDistance > wolfResult[turn][currentNode])continue;
        
        for(int i = 0; i < node[currentNode].size(); i++){
            int next = node[currentNode][i].second;
            long long nextDistance;
            if(turn == fast)nextDistance = node[currentNode][i].first/2 + currentDistance;
            else nextDistance = node[currentNode][i].first*2 + currentDistance;
            
            if(wolfResult[!turn][next] > nextDistance){
                wolfResult[!turn][next] = nextDistance;
                pq.push(make_pair(make_pair(-nextDistance, next), (!turn)));
            }
        }
    }
}


int main(){
    cin >> stump >> path;
    node = new vector<pair<int ,int>>[stump+1];
    foxResult = new long long[stump+1];
    wolfResult = new long long*[stump+1];
    wolfResult[0] = new long long[stump+1];
    wolfResult[1] = new long long[stump+1];

    for(int i = 0; i < path; i++){
        int src, dest, dis;
        cin >> src >> dest >> dis;

        node[src].push_back(make_pair(dis*2, dest));
        node[dest].push_back(make_pair(dis*2, src));
    }

    foxDijkstra(1);
    wolfDijkstra(1);

    int cnt = 0;
    for(int i = 2; i < stump + 1; i++){
        if(min(wolfResult[0][i], wolfResult[1][i]) > foxResult[i])cnt++;
    }
    cout << cnt;
}