[boj] 백준 1238 파티 (c++) - 다익스트라

[문제]

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

1238번: 파티

 

[풀이]

구해야하는 것은 2가지이다.

모든 정점에서 x까지의 최단 거리와 x에서 모든 정점까지의 최단 거리. 이 두가지의 합의 최댓값이 답이 된다.

따라서 n개의 모든 노드에 대해서 다익스트라를 돌려 x까지의 최단거리를 구하고, x에서 출발하는 다익스트라를 한 번 돌려서 더하면 된다.

 

이때, 모든 노드에 대해 다익스트라를 돌리는 것은 (모든 노드) -> x 로의 최단거리를 구하기 위함인데 역방향 간선을 따로 입력받으면 x -> (모든 노드)로의 최단거리를 다익스트라를 한 번만 돌려도 얻을 수 있다!

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#define INF 987654321

using namespace std;

int n, m, x;
vector<pair<int, int>> v1[1001];
vector<pair<int, int>> v2[1001];
int dist[1001];
int answer[1001];

void dijkstra(int start, vector<pair<int, int>> v[1001]){

    fill(dist, dist+1001, INF);

    dist[start] = 0;
    priority_queue<pair<int, int>> pq; //거리, 노드
    pq.push({0, start});

    while(!pq.empty()){
        int d = -pq.top().first;
        int curr = pq.top().second;
        pq.pop();

        if(dist[curr] < d)
            continue;

        for(int i=0; i<v[curr].size(); i++){
            int nnode = v[curr][i].first;
            int ncost = d + v[curr][i].second;
            if(dist[nnode] > ncost ){
                dist[nnode] = ncost;
                pq.push({-ncost, nnode});
            }
        }
    }

    for (int i=1; i<=n; i++){
        answer[i] += dist[i];
    }
}

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

    cin >> n >> m >> x;

    for(int i=0; i<m; i++){
        int s, e, t;
        cin >> s >> e >> t;

        v1[s].push_back({e, t});
        //역간선 정보
        v2[e].push_back({s, t});
    }

    dijkstra(x, v1);
    dijkstra(x, v2);

    int max = 0;
    //저장된 값중에 가장 큰값이 정답(최단거리)
    for (int i = 1; i <= n; i++)
    {
        if (max < answer[i])
            max = answer[i];
    }
    cout << max << '\n';
}