[Dijkstra]BOJ 16118_달빛 여우

문제 링크 : www.acmicpc.net/problem/16118

16118번: 달빛 여우

 

가중치를 번갈아 x2, /2 하여 이동하도록 하는 다익스트라 알고리즘을 구현하는 문제이다.

 

우선 가중치의 /2에 값이 유실되지 않도록 그래프의 가중치는 입력값의 2배로 설정한다.

 

기존 다익스트라 알고리즘의 우선순위 큐에 인자를 추가하여, (이 풀이에선 sprint 이다.)

해당 인자의 값에 따라 다익스트라 내의 새 dist에 x2 또는 /2 해주면 된다.

단, 늑대의 dist는 각 노드에 2배 빨리 이동해 도착한 경우와 2배 느리게 이동해 도착한 경우를 구별해 주어야 한다.

2배 빨리 도착한 경우의 가중치 합은 대부분 2배 느리게 이동한 경우보다 작으므로,

2배 느리게 도착한 가중치 합이 유실되기 때문이다.

 

 

실제로 예제의 경우, 늑대의 1 - 2 - 4 경로는 2배 가중치 기준 6 / 2 + 8 * 2 = 19이다.

하지만 실제 최단경로는 1 - 3 - 2 - 4로, 4 / 2 + 4 * 2 + 8 / 2 = 14 이다.

1 - 2의 최단경로 가중치는 1 - 2 - 4 경로에서 6 / 2 = 3이 되기 때문에, 각 경우를 구별하지 않는다면

경로 1 - 3 - 2 의 가중치 10은 실제로 더 빠르게 갈 수 있지만 다익스트라에 적용될 수 없다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
 
#define INF 9999999999999999
 
using namespace std;
typedef pair<int, int> p;
typedef long long ll;
 
int n, m;
ll dist_fox[4001];
ll dist_wolf[4001][2];
vector<p> adj[4001];
 
void dijkstra_fox() {
    priority_queue<pair<ll, int>> pque;
    dist_fox[1] = 0;
    pque.push({ 0, 1 });
 
    while (!pque.empty()) {
        pair<ll, int> cur = pque.top();
        pque.pop();
 
        ll distval = -cur.first;
        int node = cur.second;
 
        if (dist_fox[node] >= distval) {
            for (int i = 0; i < adj[node].size(); i++) {
                int nextnode = adj[node][i].first;
                ll newDist = distval + adj[node][i].second;
                if (dist_fox[nextnode] > newDist) {
                    dist_fox[nextnode] = newDist;
                    pque.push({ -newDist, nextnode });
                }
            }
        }
    }
}
 
void dijkstra_wolf() {
    priority_queue<pair<pair<ll, int>, int>> pque;
    dist_wolf[1][1] = 0;
    pque.push({ { 0, 1 }, 1 });
 
    while (!pque.empty()) {
        pair<pair<ll, int>, int> cur = pque.top();
        pque.pop();
 
        ll distval = -cur.first.first;
        int node = cur.first.second;
        int sprint = cur.second;
 
        if (dist_wolf[node][sprint] >= distval) {
            for (int i = 0; i < adj[node].size(); i++) {
                int nextnode = adj[node][i].first;
                ll newDist;
                if(sprint) newDist = distval + adj[node][i].second / 2;
                else newDist = distval + (long long)adj[node][i].second * 2;
 
                int nextsprint;
                if (sprint) nextsprint = 0;
                else nextsprint = 1;
 
                if (dist_wolf[nextnode][nextsprint] > newDist) {
                    dist_wolf[nextnode][nextsprint] = newDist;
                    pque.push({ { -newDist, nextnode }, nextsprint });
                }
            }
        }
    }
}
 
 
void init() {
    int f, s, w;
    cin >> n >> m;
 
    for (int i = 0; i < m; i++) {
        cin >> f >> s >> w;
        adj[f].push_back({ s, w * 2 });
        adj[s].push_back({ f, w * 2 });
    }
 
    for (int i = 1; i <= n; i++) {
        dist_fox[i] = INF;
        dist_wolf[i][0] = INF;
        dist_wolf[i][1] = INF;
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    dijkstra_fox();
    dijkstra_wolf();
 
    int answer = 0;
    for (int i = 2; i <= n; i++) {
        if (dist_fox[i] == INF) continue;
        if (dist_fox[i] < min(dist_wolf[i][0], dist_wolf[i][1])) answer++;
    }
 
    printf("%d\n", answer);
 
    return 0;
}