[백준 / BOJ] C++ 1238 파티

1238번: 파티

 

문제

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

1238번: 파티

 

 

풀이

1부터 N까지 각 마을에 사는 학생이 X번째 마을에 갔다가 돌아오는 최단 거리가 가장 오래 걸리는 학생의 이동 거리를 구하는 문제다. 다익스트라 알고리즘을 이용하면 해결할 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 참고하자.

[다익스트라 알고리즘 알아보기]

 

이 문제는 유향인 그래프이고 i 정점부터 출발해 X 정점까지 가는 최단 거리와 X 정점에서 출발해 i 정점에 도착하는 최단 거리를 더한 값의 최댓값을 출력하면 된다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N, M, X, ans = 0;
  cin >> N >> M >> X;

  // 간선
  vector<pair<int, int>> graph[10001]; // [정점][다음 정점, 거리]
  while (M--) {
    int u, v, w;
    cin >> u >> v >> w;
    graph[u].push_back({v, w});
  }

  // 다익스트라
  for (int i = 1; i <= N; i++) {
    vector<int> dist(10001, INT_MAX), visited(10001, 0);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

    // X까지 가는 최단거리
    dist[i] = 0;          // 시작점 거리 0
    pq.push({0, i});      // 시작점만 pq에 추가
    while (!pq.empty()) { // pq가 비면 종료
      int curr;
      do {
        curr = pq.top().second;
        pq.pop();
      } while (!pq.empty() && visited[curr]); // curr이 방문한 정점이면 무시
      // 더 이상 방문할 수 있는 정점이 없으면 종료
      if (visited[curr])
        break;

      visited[curr] = 1; // 방문처리

      for (auto &p : graph[curr]) {
        int next = p.first, d = p.second;
        // 거리가 갱신될 경우 pq에 추가
        if (dist[next] > dist[curr] + d) {
          dist[next] = dist[curr] + d;
          pq.push({dist[next], next});
        }
      }
    }

    int sum = dist[X];

    // 배열 초기화
    for (int i = 1; i <= N; i++) {
      visited[i] = 0;
      dist[i] = INT_MAX;
    }

    // X에서 돌아가는 최단거리
    dist[X] = 0;          // 시작점 거리 0
    pq.push({0, X});      // 시작점만 pq에 추가
    while (!pq.empty()) { // pq가 비면 종료
      int curr;
      do {
        curr = pq.top().second;
        pq.pop();
      } while (!pq.empty() && visited[curr]); // curr이 방문한 정점이면 무시
      // 더 이상 방문할 수 있는 정점이 없으면 종료
      if (visited[curr])
        break;

      visited[curr] = 1; // 방문처리

      for (auto &p : graph[curr]) {
        int next = p.first, d = p.second;
        // 거리가 갱신될 경우 pq에 추가
        if (dist[next] > dist[curr] + d) {
          dist[next] = dist[curr] + d;
          pq.push({dist[next], next});
        }
      }
    }

    sum += dist[i];
    ans = max(ans, sum);
  }
  cout << ans << '\n';
  return 0;
}