[백준 11780] 플로이드 2 (C#, C++) - soo:bak

문제 링크

11780번 - 플로이드 2

설명

모든 도시 쌍에 대해 최소 이동 비용과 그때의 구체적인 경로를 함께 출력하는 문제입니다. 경로가 없거나 출발과 도착이 같은 경우에는 0을 출력합니다.

접근법

플로이드 워셜 알고리즘을 사용합니다. 먼저 거리 배열을 무한대로 초기화하고 자기 자신으로의 거리는 0으로 설정합니다. 입력으로 주어진 버스 정보 중 같은 구간에 여러 버스가 있다면 최솟값만 저장합니다.

삼중 반복문으로 모든 경유지를 확인하며 최단 거리를 갱신합니다. 거리가 갱신될 때마다 해당 경로의 경유지를 따로 기록해둡니다. 이렇게 하면 나중에 경로를 복원할 수 있습니다.

경로 복원은 재귀적으로 수행합니다. 경유지가 없으면 출발지와 도착지만 반환하고, 경유지가 있으면 출발지에서 경유지까지의 경로와 경유지에서 도착지까지의 경로를 이어 붙입니다.

---

Code

C#

using System;
using System.Collections.Generic;

class Program {
  const int INF = 1_000_000_000;
  static int n, m;
  static int[,] dist = new int[101, 101];
  static int[,] mid = new int[101, 101];

  static void Floyd() {
    for (var k = 1; k <= n; k++)
      for (var i = 1; i <= n; i++)
        for (var j = 1; j <= n; j++)
          if (dist[i, j] > dist[i, k] + dist[k, j]) {
            dist[i, j] = dist[i, k] + dist[k, j];
            mid[i, j] = k;
          }
  }

  static List<int> BuildPath(int s, int e) {
    if (mid[s, e] == 0) return new List<int> { s, e };
    var k = mid[s, e];
    var left = BuildPath(s, k);
    var right = BuildPath(k, e);
    left.RemoveAt(left.Count - 1);
    left.AddRange(right);
    return left;
  }

  static void Main() {
    n = int.Parse(Console.ReadLine()!);
    m = int.Parse(Console.ReadLine()!);

    for (var i = 1; i <= n; i++)
      for (var j = 1; j <= n; j++)
        dist[i, j] = (i == j) ? 0 : INF;

    for (var i = 0; i < m; i++) {
      var parts = Console.ReadLine()!.Split();
      var a = int.Parse(parts[0]);
      var b = int.Parse(parts[1]);
      var c = int.Parse(parts[2]);
      if (c < dist[a, b]) dist[a, b] = c;
    }

    Floyd();

    for (var i = 1; i <= n; i++) {
      for (var j = 1; j <= n; j++)
        Console.Write((dist[i, j] == INF ? 0 : dist[i, j]) + " ");
      Console.WriteLine();
    }

    for (var i = 1; i <= n; i++) {
      for (var j = 1; j <= n; j++) {
        if (i == j || dist[i, j] == INF) {
          Console.WriteLine(0);
          continue;
        }
        var path = BuildPath(i, j);
        Console.Write(path.Count + " ");
        Console.WriteLine(string.Join(" ", path));
      }
    }
  }
}

C++

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

typedef vector<int> vi;
typedef vector<vi> vvi;

const int INF = 1e9;

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

  int n, m; cin >> n >> m;
  vvi dist(n + 1, vi(n + 1, INF));
  vvi mid(n + 1, vi(n + 1, 0));

  for (int i = 1; i <= n; i++) dist[i][i] = 0;

  for (int i = 0; i < m; i++) {
    int a, b, c; cin >> a >> b >> c;
    dist[a][b] = min(dist[a][b], c);
  }

  for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        if (dist[i][j] > dist[i][k] + dist[k][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
          mid[i][j] = k;
        }

  auto build = [&](auto self, int s, int e) -> vi {
    if (mid[s][e] == 0) return {s, e};
    int k = mid[s][e];
    auto left = self(self, s, k);
    auto right = self(self, k, e);
    left.pop_back();
    left.insert(left.end(), right.begin(), right.end());
    return left;
  };

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++)
      cout << (dist[i][j] == INF ? 0 : dist[i][j]) << " ";
    cout << "\n";
  }

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (i == j || dist[i][j] == INF) {
        cout << 0 << "\n";
        continue;
      }
      auto path = build(build, i, j);
      cout << path.size() << " ";
      for (int x : path) cout << x << " ";
      cout << "\n";
    }
  }

  return 0;
}