[백준 1238] 파티 (C#, C++) - soo:bak

문제 링크

1238번 - 파티

설명

N명의 학생이 각자의 마을에서 파티가 열리는 마을 X로 갔다가 돌아옵니다. 도로는 단방향이고 각각 소요 시간이 있을 때, 왕복 시간이 가장 오래 걸리는 학생의 소요 시간을 구하는 문제입니다.

접근법

각 학생의 왕복 시간은 집→X 시간과 X→집 시간의 합입니다. 단순하게 각 학생마다 다익스트라를 수행하면 N번이 필요하지만, 역방향 그래프를 활용하면 두 번만으로 충분합니다.

X→집 시간은 정방향 그래프에서 X를 시작점으로 다익스트라를 한 번 수행하면 모든 학생에 대해 구할 수 있습니다.

집→X 시간을 구하려면 원래는 각 학생마다 다익스트라가 필요합니다. 하지만 모든 간선의 방향을 뒤집은 역방향 그래프를 만들면, 역방향에서 X→A 경로는 원래 그래프에서 A→X 경로와 같습니다. 따라서 역방향 그래프에서 X를 시작점으로 다익스트라를 수행하면 모든 학생의 집→X 시간을 한 번에 구할 수 있습니다.

각 학생에 대해 두 거리를 더한 값 중 최대값이 답입니다.

---

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class Program {
    const int INF = int.MaxValue / 4;

    static int[] Dijkstra(int n, int start, List<(int to, int w)>[] graph) {
      var dist = new int[n + 1];
      Array.Fill(dist, INF);
      dist[start] = 0;
      var pq = new PriorityQueue<int, int>();
      pq.Enqueue(start, 0);
      while (pq.Count > 0) {
        pq.TryDequeue(out var cur, out var d);
        if (d > dist[cur])
          continue;
        foreach (var edge in graph[cur]) {
          var nd = d + edge.w;
          if (nd < dist[edge.to]) {
            dist[edge.to] = nd;
            pq.Enqueue(edge.to, nd);
          }
        }
      }
      return dist;
    }

    static void Main(string[] args) {
      var first = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      var n = first[0];
      var m = first[1];
      var x = first[2];

      var adj = new List<(int, int)>[n + 1];
      var radj = new List<(int, int)>[n + 1];
      for (var i = 1; i <= n; i++) {
        adj[i] = new List<(int, int)>();
        radj[i] = new List<(int, int)>();
      }

      for (var i = 0; i < m; i++) {
        var line = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
        var a = line[0];
        var b = line[1];
        var t = line[2];
        adj[a].Add((b, t));
        radj[b].Add((a, t));
      }

      var distFromX = Dijkstra(n, x, adj);
      var distToX = Dijkstra(n, x, radj);

      var ans = 0;
      for (var i = 1; i <= n; i++)
        ans = Math.Max(ans, distToX[i] + distFromX[i]);
      Console.WriteLine(ans);
    }
  }
}

C++

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

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;

const int INF = 1e9;

vi dijkstra(int n, int start, const vector<vp>& g) {
  vi dist(n + 1, INF);
  priority_queue<pii, vp, greater<pii>> pq;
  dist[start] = 0;
  pq.push({0, start});
  while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u])
      continue;
    for (auto [v, w] : g[u]) {
      int nd = d + w;
      if (nd < dist[v]) {
        dist[v] = nd;
        pq.push({nd, v});
      }
    }
  }
  return dist;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m, x; cin >> n >> m >> x;
  vector<vp> adj(n + 1), radj(n + 1);
  for (int i = 0; i < m; i++) {
    int a, b, t; cin >> a >> b >> t;
    adj[a].push_back({b, t});
    radj[b].push_back({a, t});
  }

  auto distFromX = dijkstra(n, x, adj);
  auto distToX = dijkstra(n, x, radj);

  int ans = 0;
  for (int i = 1; i <= n; i++)
    ans = max(ans, distToX[i] + distFromX[i]);

  cout << ans << "\n";

  return 0;
}