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

문제&링크

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

 

풀이

1. 각자 마을 별로 특정 마을까지 갔다가 오는 최소 거리를 계산해야 하기에, 다익스트라 알고리즘을 사용한다.

2. 시작점과 끝점 가중치가 주어져 있기에 끝점과 가중치를 pair로 하는 벡터 행렬에 시작점을 기준으로 저장한다.

3. 다익스트라 함수에서 시작점과 끝점을 파라미터로 받는다.

4. fill 함수를 이용해서 모든 거리를 INF로 초기화한다.

5. 우선순위 큐를 활용하여 가중치가 가장 낮은 값 먼저 탐색하도록 한다. 이때 우선순위 큐는 기본적으로 max heap 이기에 가중치를 음수로 하여 저장하고, 값을 사용할 때는 -를 붙여 양수로 사용한다.

6. 시작점 s의 가중치를 0으로 초기화한 후 우선순위 큐에 삽입하고, 거리 또한 0으로 초기화한다.

7. 현재 노드(cx), 현재 가중치(cdist)를 우선순위 큐에서 뽑아온다.

8. 만약 cx가 원하던 끝점이라면 반복문을 탈출한다.

9. 현재 노드에서 갈 수 있는 노드를 반복문을 이용해 탐색하고 방문 노드(nx)까지의 거리(dist[nx])가 현재 노드를 거쳐 방문 노드까지 도달하는 거리(ndist)보다 길다면 dist[nx]를 ndist로 설정한다.

10. 해당 가중치(ndist)를 음수로 하고, 해당 노드를 함께 우선순위 큐에 삽입한다.

11. 7 - 10의 과정을 반복한다.

12. 다익스트라 알고리즘을 이용하여 X 마을에 가는 최소 비용 + X 마을에서 오는 최소 비용을 구하고 최댓값을 구한다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 100000000

using namespace std;

int N, M, X;
vector<pair<int, int>> V[1001];
int dist[1001];

int dijkstra(int s, int e) {
    int res;
    fill(dist, dist + 1001, INF);
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, s));
    dist[s] = 0;
    
    while(!pq.empty()) {
        int cx = pq.top().second;
        int cdist = -pq.top().first;
        pq.pop();
        
        if (cx == e) {
            res = dist[cx];
            break;
        }
        
        for (int i = 0; i < V[cx].size(); i++) {
            int nx = V[cx][i].first;
            int ndist = V[cx][i].second + cdist;
            
            if (dist[nx] > ndist) {
                dist[nx] = ndist;
                pq.push(make_pair(-ndist, nx));
            }
        }
    }
    
    return res;
}

int main() {
    int start, end, T;
    
    cin >> N >> M >> X;
    
    for (int i = 0; i < M; i++) {
        cin >> start >> end >> T;
        
        V[start].push_back(make_pair(end, T));
    }
    
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        int toX = dijkstra(i, X); 
        int fromX = dijkstra(X, i);
        if (ans < toX + fromX) ans = toX + fromX;
    }
    cout << ans;    
}