[백준 1238번] 파티 (C++)

문제링크 : https://www.acmicpc.net/problem/1238

1238번: 파티

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M, X, result;
int dist[2][1001];
vector<pii>v[2][1001];

void Dijkstra(int d, int s)
{
    priority_queue<pii, vector<pii>, greater<pii>> pq; //비용이 적은순으로
    pq.push({0, s});
    dist[d][s] = 0; //시작
    while(!pq.empty())
    {
        auto [cost, cur] = pq.top();
        pq.pop();
        if(dist[d][cur] < cost) continue;
        for(int i=0; i<v[d][cur].size(); i++)
        {
            int next = v[d][cur][i].first; //다음 위치
            int ncost = cost + v[d][cur][i].second; //다음 비용
            if(dist[d][next] > ncost) //비용 갱신
            {
                dist[d][next] = ncost;
                pq.push({ncost, next});
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> M >> X;
    for(int i=0; i<M; i++)
    {
        int a, b, c;
        cin >> a >> b >> c; //시작, 끝, 비용
        v[0][a].push_back({b, c}); //정방향
        v[1][b].push_back({a, c}); //역방향
    }

    for(int i=1; i<=N; i++)
    {
        dist[0][i] = MAX;
        dist[1][i] = MAX;
    }

    Dijkstra(0, X); //시작점 ~ X
    Dijkstra(1, X); //X ~ 시작점

    for(int i=1; i<=N; i++)
    {
        result = max(result, dist[0][i] + dist[1][i]); //갔다 온 거리중 최대값 저장
    }
    cout << result;

    return 0;
}

기본적인 다익스트라에서 조금 응용된 문제이다.

일반적인 다익스트라에서는 목표 지점까지의 총 비용을 구했지만, 해당 문제는 목표 지점에 도착하고 다시 시작점으로 돌아오는 것까지 계산해주어야 한다.

 

이를 위해 처음 간선을 입력받는데 정방향으로 1개, 역방향으로 1개씩 값을 저장해준다.

이후 시작점 ~ X까지의 다익스트라 탐색 1번

X ~ 시작점까지의 다익스트라 탐색 1번 돌려주고, 각 탐색했을 때 든 비용을 저장한 배열에서 최대값을 찾아주면 된다.