문제

16118번: 달빛 여우

풀이

늑대놈 때문에 많이 힘들었다.

늑대는 여우보다 2배의 속도, 절반의 속도로 움직인다. 따라서 처음 입력으로 주어지는 그루터기 사이의 거리를 조절하여 늑대의 속도를 조절했다.
거리를 2배로 하여 절반의 속도, 거리를 1/2배 하여 두배의 속도를 표현했다. 하지만 모든 거리가 정수로 표현되는 것이 큰 수를 표현하기에 알맞기 때문에 처음 주어지는 거리에 1배, 2배, 4배를 하여 늑대(두배 속도), 여우, 늑대(절반 속도)를 표현하였다.

또한 늑대는 움직일 때마다 속도가 달라지므로 같은 그루터기에 도착하더라도 해당 그루터기를 두배의 속도로 왔는지, 절반의 속도로 왔는지에 따라 값이 달라진다.
그래서 늑대는 최단 거리도 2개로 구해주어야 한다. 그루터기에 2배의 속도로 들어왔을 때, 절반의 속도로 들어왔을 때 다른 값을 각각 저장해주어야 한다.

다익스트라로 각 노드를 우선순위 큐에 넣을 때 현재 속도(두배인지, 절반인지)에 대한 정보도 포함하여 같이 넣어준다. pop() 할때 그 정보를 토대로 다음 위치까지의 거리를 구하고 해당 최단 경로를 어디에 저장할지 결정한다.

코드

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

using namespace std;

struct Node
{
    int to;
    int64_t weight;
    bool isDouble;

    bool operator>(Node input)
    {
        return this->weight > input.weight;
    }
};

template <typename T>
struct cmp
{
    bool operator()(T a, T b)
    {
        return a > b;
    }
};

int n, m;
vector<vector<Node>> graph[3];

int64_t min(int64_t a, int64_t b)
{
    return a < b ? a : b;
}

vector<int64_t> dijkstra(int start)
{
    priority_queue<Node, vector<Node>, cmp<Node>> pq;
    vector<int64_t> dist(n+1, INT64_MAX);
    pq.push({start, 0});
    dist[start] = 0;
    
    while (!pq.empty())
    {
        int cur = pq.top().to;
        int64_t curWeight = pq.top().weight;
        pq.pop();

        if (curWeight > dist[cur])
            continue;

        for (auto n : graph[1][cur])
        {
            int next = n.to;
            int64_t nextWeight = curWeight + n.weight;

            if (nextWeight >= dist[next])
                continue;

            dist[next] = nextWeight;
            pq.push({next, nextWeight});
        }
    }

    return dist;
}

vector<vector<int64_t>> dijkstra2(int start)
{
    priority_queue<Node, vector<Node>, cmp<Node>> pq;
    vector<vector<int64_t>> dist(2);
    dist[0] = vector<int64_t>(n+1, INT64_MAX);
    dist[1] = vector<int64_t>(n+1, INT64_MAX);
    pq.push({start, 0, true});
    dist[true][1] = 0;
    
    while (!pq.empty())
    {
        int cur = pq.top().to;
        int64_t curWeight = pq.top().weight;
        bool curIsDouble = pq.top().isDouble;
        pq.pop();
        
        if (curWeight > dist[curIsDouble][cur])
            continue;

        for (auto n : graph[!curIsDouble * 2][cur])
        {
            int next = n.to;
            int64_t nextWeight = curWeight + n.weight;

            if (nextWeight >= dist[!curIsDouble][next])
                continue;

            dist[!curIsDouble][next] = nextWeight;
            pq.push({next, nextWeight, !curIsDouble});
        }
    }

    return dist;
}

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

    cin >> n >> m;
    for (int i=0; i<3; ++i)
        graph[i].assign(n+1, vector<Node>());

    while (m--)
    {
        int a, b;
        int64_t weight;
        cin >> a >> b >> weight;
        for (int i=0; i<3; ++i)
        {
            graph[i][a].push_back({b, weight * 1 << i});
            graph[i][b].push_back({a, weight * 1 << i});
        }
    }

    vector<int64_t> foxDist = dijkstra(1);
    vector<vector<int64_t>> wolfDist = dijkstra2(1);
    
    int cnt = 0;
    for (int i=1; i<n+1; ++i)
    {
        if (min(wolfDist[0][i], wolfDist[1][i]) > foxDist[i])
        {
            ++cnt;
        }
    }

    cout << cnt << endl;
    return 0;
}