[백준][C++] 1238: 파티

문제

풀이

• 다익스트라 알고리즘을 사용한다.
• 학생의 수 N만큼 각각의 학생이 X까지 가는 소요시간을 다익스트라로 계산하는 방법
• 혹은 역방향 간선을 사용하여 X까지의 소요시간이 최대인 학생을 찾는 방법
• 역방향 간선을 이용하는 방법은 2번만 다익스트라를 계산하면 되기에 속도차이가 크다.

코드

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

using namespace std;

vector<vector<pair<int, int>>> edges;
vector<vector<pair<int, int>>> reverse_edges;
vector<vector<int>> dists;
vector<vector<int>> reverse_dists;

void dijkstra(int start)
{
    dists[start][start] = 0;
    priority_queue<pair<int, int>> q;
    q.push(make_pair(0, start));

    while (!q.empty())
    {
        int current_node = q.top().second;
        int current_dist = -q.top().first;
        q.pop();

        if (dists[start][current_node] < current_dist)
        {
            continue;
        }

        for (int i = 0; i < edges[current_node].size(); ++i)
        {
            int next_node = edges[current_node][i].second;
            int next_dist = current_dist + edges[current_node][i].first;
            if (next_dist < dists[start][next_node])
            {
                dists[start][next_node] = next_dist;
                q.push(make_pair((-1) * next_dist, next_node));
            }
        }
    }
}

void reverse_dijkstra(int start)
{
    reverse_dists[start][start] = 0;
    priority_queue<pair<int, int>> q;
    q.push(make_pair(0, start));

    while (!q.empty())
    {
        int current_node = q.top().second;
        int current_dist = (-1) * q.top().first;
        q.pop();

        if (reverse_dists[start][current_node] < current_dist)
        {
            continue;
        }

        for (int i = 0; i < reverse_edges[current_node].size(); ++i)
        {
            int next_node = reverse_edges[current_node][i].second;
            int next_dist = current_dist + reverse_edges[current_node][i].first;
            if (next_dist < reverse_dists[start][next_node])
            {
                reverse_dists[start][next_node] = next_dist;
                q.push(make_pair((-1) * next_dist, next_node));
            }
        }
    }
}

int main()
{
    // N명의 학생, M명의 다리, X번 마을에 모인다.
    int N, M, X;
    int answer = 0;

    cin >> N >> M >> X;

    edges.resize(N);
    dists.resize(N);
    for (int i = 0; i < N; ++i)
    {
        dists[i].resize(N, INT_MAX);
    }

    reverse_edges.resize(N);
    reverse_dists.resize(N);
    for (int i = 0; i < N; ++i)
    {
        reverse_dists[i].resize(N, INT_MAX);
    }

    for (int i = 0; i < M; ++i)
    {
        int n1, n2, dist;
        cin >> n1 >> n2 >> dist;

        edges[n1 - 1].push_back(make_pair(dist, n2 - 1));
        reverse_edges[n2 - 1].push_back(make_pair(dist, n1 - 1));
    }

    // N명 만큼 다익스트라 계산
    /*for (int i = 0; i < N; ++i)
    {
        dijkstra(i);
    }
    for (int i = 0; i < N; ++i)
    {
        answer = max(answer, dists[i][X - 1] + dists[X - 1][i]);
    }*/

    dijkstra(X - 1);
    reverse_dijkstra(X - 1);

    for (int i = 0; i < N; ++i)
    {
        answer = max(answer, dists[X - 1][i] + reverse_dists[X - 1][i]);
    }

    cout << answer;

    return 0;
}