백준 16118 / C++

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

16118번: 달빛 여우

 

[ 풀이 ]

 

여우는 v로 가고 늑대는 2v v/2 를 반복한다. 이 때 시간은 여우는 d/v , 늑대는 2d/v 또는 d/2v가 걸린다. 

모두 정수로 맞춰주면, 시간은 여우가 2t 2t .... 늑대는 t / 4t / t / 4t .. 이렇게 걸린다.

여우의 경우 그냥 다익을 돌려주면 최단시간이 나온다. 

늑대의 경우가 이 문제의 핵심이다. t와 4t의 구분은 홀짝성이다. 

같은 지점을 가더라도 짝수번째 도착할때와 홀수번째 도착할때 최단시간이 다르므로, 

늑대의 경우 dist[x][2]로 만들어서 짝수번째와 홀수번째 모두 구해준다.  

마지막으로 여우가 늑대보다 먼저 도착할 조건은, 

여우 시간 < 늑대 시간 이다. 늑대 시간은 min(dist[x][0], dist[x][1])로 구해주면 된다. 

 

 

[ 코드 ] 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pll = pair<ll, ll>;
using plll = tuple<ll, ll, ll>;
ll n, m, a, b, d;
vector<pll> g[4004];
ll fox_dist[4004];
ll wolf_dist[4004][2];

// 여우 
void dijk1(int st) {
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    fill(fox_dist, fox_dist + 4004, 1e18);
    fox_dist[st] = 0;
    pq.push({ 0, st });
    while (pq.size()) {
        ll d, x;
        tie(d, x) = pq.top(); pq.pop();
        if (fox_dist[x] != d) continue;
        for (auto nxt : g[x]) {
            ll nx, w;
            tie(nx, w) = nxt;
            // 가중치 2로 동일 
            if (fox_dist[nx] > fox_dist[x] + 2 * w) {
                fox_dist[nx] = fox_dist[x] + 2 * w;
                pq.push({ fox_dist[nx], nx });
            }
        }
    }
}

// 늑대
void dijk2(int st) {
    priority_queue<plll, vector<plll>, greater<plll>> pq;
    for (int i = 0; i < 4004; i++) {
        for (int j = 0; j < 2; j++) {
            wolf_dist[i][j] = 1e18;
        }
    }
    wolf_dist[st][0] = 0;
    pq.push({ 0, 0, st });
    while (pq.size()) {
        ll d, i, x;
        tie(d, i, x) = pq.top(); pq.pop();
        if (wolf_dist[x][i] != d) continue;
        for (auto nxt : g[x]) {
            ll nx, w;
            tie(nx, w) = nxt;
            // 가중치 변함 
            int temp = (i == 0) ? 1 : 4;
            // 다음턴으로 갈때 홀짝성 바꿔줌 0->1  1->0
            if (wolf_dist[nx][i ^ 1] > wolf_dist[x][i] + temp * w) {
                wolf_dist[nx][i ^ 1] = wolf_dist[x][i] + temp * w;
                pq.push({ wolf_dist[nx][i ^ 1], i ^ 1, nx });
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    while (m--) {
        cin >> a >> b >> d;
        g[a].push_back({ b, d });
        g[b].push_back({ a, d });
    }
    dijk1(1);
    dijk2(1);
    int ans = 0;
    for (int i = 2; i <= n; i++) {
        // 여우시간 < 늑대시간 
        if (fox_dist[i] < min(wolf_dist[i][0], wolf_dist[i][1])) {
            ans++;
        }
    }
    cout << ans << '\n';
}