달빛여우.md

DONE_DATE	2025/02/04

달빛 여우

난이도

• 골드 1

문제

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

알고리즘 분류

• 그래프 이론
• 최단 경로
• 데이크스트라

회고

• 여우 다익스트라는 어렵지 않지만 늑대 다익스트라가 쉽지가 않다.
• 늑대의 속도가 2배가 되었다가 0.5배가 되었다가 해서
• 그래서 아예 처음 길이를 2배로 늘려서 저장하고
• 늑대가 뛰어서 갈 때는 0.5배, 걸어서 갈 때는 2배로 계산해서
• 딱 떨어지게끔 구현했다.
• 늑대가 어떤 Edge를 지나는 것이 이전 Edge를 빠르게 지났다면 이번에는 느리게 가고
• 이전 Edge를 느리게 지났다면 이번에는 빠르게 가는 식이라서
• dist가 2개 필요하다.
• 드디어 골드 1을 달았다.

전체코드

#include <bits/stdc++.h>

using namespace std;

int n, m;
int Fdist[4001];
int Wdist[2][4001]; // 걸어서 또는 뛰어서 노드 v에도 도착한 최단 시간 [state][nodes]
typedef pair<int, int> Edge; // cost, node
typedef tuple<int, int, int> WolfEdge; // cost, node, state
vector<vector<Edge>> Graph;

void Fox_dijkstra() {
    priority_queue<Edge, vector<Edge>, greater<>> pq; // (비용, 노드)
    pq.emplace(0, 1);
    Fdist[1] = 0;

    while (!pq.empty()) {
        auto [cost, here] = pq.top();
        pq.pop();

        // 이미 갱신된 최단 거리보다 크면 무시
        if (Fdist[here] < cost) {
            continue;
        }

        // 현재 노드 here와 연결된 모든 간선 확인
        for (auto &i: Graph[here]) {
            int next = i.second;
            int next_cost = cost + i.first;

            // 더 짧은 경로 발견 시 갱신
            if (Fdist[next] > next_cost) {
                Fdist[next] = next_cost;
                pq.emplace(next_cost, next);
            }
        }
    }
}

void Wolf_dijkstra() {
    // 우선순위 큐: (비용, 현재 노드, 다음 이동 상태)
    // state: 0 -> 느린 이동 차례(걸어가기), 1 -> 빠른 이동 차례(뛰어가기)
    priority_queue<WolfEdge, vector<WolfEdge>, greater<>> pq;
    pq.emplace(0, 1, 1); // 지금은 1번 노드, 비용은 0, 다음 이동상태는 1
    Wdist[1][1] = 0; // 1번 노드에 '뛰어서 도착한 상태(1)' 비용 0으로 시작

    while (!pq.empty()) {
        auto [cost, here, state] = pq.top();
        pq.pop();

        // 이미 갱신된 최단 거리보다 크면 무시
        if (Wdist[state][here] < cost) {
            continue;
        }

        // 현재 노드에서 갈 수 있는 모든 간선을 확인
        for (auto &i: Graph[here]) {
            int next = i.second;

            // state=1(이번 이동은 빠른 속도, 다음에 걸어야 함)
            if (state == 1) {
                int next_cost = cost + i.first / 2;
                if (Wdist[0][next] > next_cost) {
                    Wdist[0][next] = next_cost;
                    pq.emplace(next_cost, next, 0);
                }
            } else { // state=0(이번 이동은 느린 속도, 다음에 뛰어야 함)
                int next_cost = cost + i.first * 2;
                if (Wdist[1][next] > next_cost) {
                    Wdist[1][next] = next_cost;
                    pq.emplace(next_cost, next, 1);
                }
            }
        }
    }
}

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

    cin >> n >> m;
    Graph.resize(n + 1);

    // 입력받은 간선 정보는 문제에서 d만큼 시간이 걸린다고 했으므로
    // 내부에서는 2*d로 저장 (여우, 늑대 이동 로직에서 /2, *2 등을 적용)
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        Graph[u].emplace_back(w * 2, v);
        Graph[v].emplace_back(w * 2, u);
    }

    for (int i = 1; i <= n; i++) {
        Fdist[i] = INT_MAX;
        Wdist[0][i] = INT_MAX;
        Wdist[1][i] = INT_MAX;
    }

    Fox_dijkstra();
    Wolf_dijkstra();

    int answer = 0;
    for (int i = 2; i <= n; i++) {
        // 여우 소요 시간 vs. 늑대 소요 시간(두 상태 중 최소)
        if (Fdist[i] < min(Wdist[0][i], Wdist[1][i])) {
            answer++;
        }
    }

    cout << answer;
    return 0;
}