[BOJ/C++] 파티(1238번)

1. 개요 

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

1238번: 파티

1-1. 설명

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고있다. 어느날 이 N명의 학생이 X번 마을에 모여 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있으며, i번째 길을 지나가는데 T_i의 시간을 소비한다. 각각 학생들은 파티에 참석하기 위해 걸어서 다시 마을로 돌아와야 한다. 이때, 최단 시간에 오고가기를 원할 때 N명의 학생들 중 오고가는데 가장 많은 시간을 소비하는 학생은 누구인지 구하는 프로그램을 작성한다. 

1-2. 제한 사항 

 - 첫줄에 N, M, X가 주어지며, N은 1 이상 1,000 이하, M은 1 이상 10,000 이하, X는 1 이상 N 이하

 - 둘째줄부터 M+1까지 i 번째 도로 시작점, 끝점, 소요시간이 주어짐

---

2. 구현

2-1. 풀이

최단 경로를 구하는 점과 소요시간을 가중치로 생각하면 다익스트라로 푸는 것임을 바로 알 수 있다. 1번째 학생부터 N번째 학생까지 다익스트라 최단 거리를 구한 후, 제일 많은 시간을 소비하는 학생을 저장하여 출력하였다. 

2-2. 코드

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

constexpr size_t MAX_NUM = 1001;
constexpr size_t INF = 99999999;
vector<pair<int, int>> graphs[MAX_NUM];
int dist[MAX_NUM];

void dijkstra(int X, int start);

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

    int N, M, X, curDist, resultDist = 0;
    cin >> N >> M >> X;

    // 도로의 시작점, 끝점, 시간
    int start, end, time;
    for (int i = 0; i < M; i++) {
        cin >> start >> end >> time;
        graphs[start].push_back(make_pair(end, time));
    }

    for (int i = 1; i <= N; i++) {
        fill(dist, dist + N + 1, INF);
        dijkstra(X, i); // X까지 가는 거리
        curDist = dist[X];
        fill(dist, dist + N + 1, INF);
        dijkstra(i, X); // i까지 돌아가는 거리
        curDist += dist[i];
        if (curDist > resultDist) resultDist = curDist;
    }

    cout << resultDist;
    return 0;
}

void dijkstra(int X, int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int >>> priQue;
    priQue.push(make_pair(0, start));
    dist[start] = 0;

    while (!priQue.empty()) {
        int cost = priQue.top().first;
        int node = priQue.top().second;
        priQue.pop();

        for (int i = 0; i < graphs[node].size(); i++) {
            int nextNode = graphs[node][i].first;
            int nextCost = graphs[node][i].second;
            int nextDist = cost + nextCost;
            if (dist[nextNode] > nextDist) {
                dist[nextNode] = nextDist;
                priQue.push(make_pair(dist[nextNode], nextNode));
            }
        }
    }
}