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

문제

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

---

문제 요약

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

 

N명의 학생이 X번 마을에 모여서 파티를 벌이기로 했다.

 

마을 사이에는 총 m개의 단방향 도로들이 있고, i번째 길을 지나는데  일정 시간을 소비한다.

 

모든 학생이 파티에 참여하고 집으로 돌아오기로 했을 때,

 

가장 많은 시간을 소비하는 학생의 소요 시간을 출력한다.

---

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N, M, X;

vector<pair<int, int>> edges[1010];

priority_queue<pair<int, int>> pq;

// dist[i][j]: i에서 j로 갈 수 있는 최단 거리
int dist[1010][1010];

int dijkstra(int start, int end) {
    // 시작점 우선순위 큐에 삽입 (최소힙을 위해 -를 붙여 삽입)
    pq.push(make_pair(-0, start));

    while (!pq.empty()) {
        int w = pq.top().first;
        int x = pq.top().second;

        pq.pop();

        w = -w;

        for (int i = 0; i < edges[x].size(); i++) {

            int nx = edges[x][i].first;
            int nw = edges[x][i].second;

            if (dist[start][nx] > w + nw) {
                dist[start][nx] = w + nw;
                pq.push(make_pair(-(w + nw), nx));
            }
        }
    }

    return dist[start][end];
}

int main() {
    // 입출력 단축 코드
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M >> X;

    // dist 배열 초기화
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (i == j) {
                dist[i][j] = 0;
                continue;
            }
            dist[i][j] = 1e9;
        }
    }

    // 그래프 정보 입력
    for (int i = 0; i < M; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        edges[a].push_back(make_pair(b, w));
    }

    // 모든 학생의 소요시간 중 최단 시간 탐색
    int res = 0;

    for (int i = 1; i <= N; i++) {
        res = max(res, dijkstra(i, X) + dijkstra(X, i));
    }

    cout << res;

    return 0;
}

---

코드 설명

다익스트라 알고리즘을 통해 문제를 해결한다.

 

1. dist[i][j]를 i번 마을에서 j번 마을로 이동하는데 걸리는 최소 시간으로 정의한다.

 

2. dist 배열을 모두 무한대(10^9)으로 초기화한다.

 

3. 모든 학생들에 대해 X번 마을로 오고 갈 때 소요되는 시간을 다익스트라 알고리즘을 두 번 실행하여 구한다.

 

4. 그 중 가장 최단 시간을 출력한다.