[백준] 골드3 : (1238) 파티

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

1238번: 파티

 

#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;

int N, M, X, Cnt;
map<int, vector<pair<int, int>>> m;
vector<int> D1, D2;

int Dijkstra(int start, int dest)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<bool> visit(N + 1, false);
    vector<int> dist(N + 1, 987654321);

    pq.push({ 0, start });
    dist[start] = 0;

    while (!pq.empty())
    {
        int c = pq.top().first;
        int n = pq.top().second;
        pq.pop();

        if (visit[n]) continue;
        visit[n] = true;

        for (const auto& i : m[n])
        {
            if (dist[i.first] > c + i.second)
            {
                dist[i.first] = c + i.second;
                pq.push({ dist[i.first], i.first });
            }
        }
    }
    return dist[dest];
}

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

    cin >> N >> M >> X;

    D1.resize(N + 1, 987654321);
    D2.resize(N + 1, 987654321);
    for (int i = 0, a, b, c; i < M; ++i)
    {
        cin >> a >> b >> c;
        m[a].push_back({ b, c });
    }

    for (int i = 1; i <= N; ++i)
    {
        if (i == X) continue;
        D1[i] = Dijkstra(i, X);
    }

    for (int i = 1; i <= N; ++i)
    {
        if (i == X) continue;
        D2[i] = Dijkstra(X, i);
    }

    int answer = 0;
    for (int i = 1; i <= N; ++i)
    {
        if (i == X) continue;
        answer = max(answer, D1[i] + D2[i]);
    }

    cout << answer << "\n";
}

각 마을과 도착 마을 간의 다익스트라로 경로를 구하고, 반대로 도착 마을부터 각 마을까지의 다익스트라를 구한다.

 

이 둘의 합이 가장 높은 값을 출력한다.