[BOJ/16118] 달빛 여우, c++

🔗 링크

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

16118번: 달빛 여우

https://github.com/jokj624/PS/blob/master/10000-15000/16118.cpp

GitHub - jokj624/PS: BOJ, CodeForces 알고리즘 문제 소스코드

🤯 한줄 후기

늑대가 여우보다 약하다니

🤷 문제

👩‍💻 풀이

다익스트라 알고리즘으로 풀수 있는 문제다.

늑대는 여우보다 2배 빠르게 가거나 2배 느리게 가는걸 반복한다. 여우는 일정한 속도로 걷기 때문에 처음에 cost 자체를 2배하여 넣어준다. 그러면 늑대는 /2 혹은 *2 로 cost를 계산하면 된다.

굳이 2배를 하는 이유는 /2에서 실수가 나올 수도 있어 정확하지 않음! 미리 2배를 하는게 편하다. 

먼저 여우는 속도가 일정하기 때문에 미리 다익스트라를 한번 돌려서 각 그루터기까지의 최단 거리를 구해준다.

 

늑대를 계산해야하는데 기존의 다익스트라로 계산하되 2개를 모두 계산해줘야한다. 여기서 의미하는 2개는 늑대가 해당 그루터기까지 2배의 속력으로 갔을 때, 절반의 속력으로 갔을때이다.

2차원 배열을 만들어주고, 0/1 로 구분하여 저장한다. priority_queue 안에 현재 그루터기에서  다음 그루터기까지 최단 거리 , 다음 그루터기 번호, 속력에 따라 0인지 1인지를 저장해주면 된다.

늑대는 번갈아가면서 속력이 바뀌기 때문에 q의 front의 0/1 변수값에 따라 다음 그루터기까지는 !변수 로 바꿔서 넣어주면 된다.

 

최종적으로 구하고자 하는 답은 여우가 늑대보다 먼저 도착할 수 있는 그루터기 개수이기 때문에 마지막에

min(wolf[그루터기번호][0], wolf[그루터기번호][1]) 과 기존에 구해둔 여우의 해당 그루터기 d[그루터기번호]까지 최단거리를 비교하여 여우가 더 작으면 카운팅 해준다.

 

💻 코드

//AC
//BOJ 16118 달빛 여우 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 2e9+1
typedef long long ll;
typedef pair<ll, ll> edge;
vector<edge> graph[4001];
int main() {
    int n, m;
    cin >> n >> m;
    ll d[n + 1];
    ll wolf[n + 1][2];
    bool c[n + 1];
    for (int i = 0; i < m; i++){
        int from, to, cost;
        cin >> from >> to >> cost;
        graph[from].push_back({to, cost*2});
        graph[to].push_back({from, cost*2});
    }
    for (int i = 1; i <= n; i++){
        d[i] = INF;
        wolf[i][0] = INF;    wolf[i][1] = INF;
        c[i] = false;
    }
    priority_queue<edge, vector<edge>, greater<edge>> pq;
    pq.push({0, 1});
    d[1]=0;
    while (!pq.empty()) {  // 여우
        ll x = pq.top().second;
        pq.pop();
        if (!c[x]){
            c[x] = true;
            for (int j = 0; j < graph[x].size(); j++){
                int y = graph[x][j].first;
                if (d[y] > d[x] + graph[x][j].second) {
                    d[y] = d[x] + graph[x][j].second;
                    pq.push({d[y], y});
                }
            }
        }
    }
    priority_queue<pair<ll, pair<ll, ll>>> pq2;
    pq2.push({0, {1, 0}});  // 늑대 
    wolf[1][0] = 0;
    while (!pq2.empty()) {
        ll cc = -pq2.top().first;
        ll x = pq2.top().second.first;
        ll z = pq2.top().second.second;
        pq2.pop();
        if(wolf[x][z] < cc) continue;
        for (int j = 0; j < graph[x].size(); j++) {
            int y = graph[x][j].first;
            ll nextCost = 0;
            if(z)   nextCost = graph[x][j].second * 2;
            else    nextCost = graph[x][j].second / 2;
            if (wolf[y][!z] > cc + nextCost) {
                wolf[y][!z] = cc + nextCost;
                pq2.push({-wolf[y][!z], {y, !z}});
            }
        }
    }
    ll ans = 0;
    for(int i=1; i<=n; i++){
        if(d[i] < min(wolf[i][0], wolf[i][1]) && d[i] != INF){
            ans += 1;
        }
    }
    printf("%lld", ans);
    return 0;
}