[백준 11657] 타임머신 (C#, C++) - soo:bak

문제 링크

11657번 - 타임머신

설명

도시와 버스 노선 정보가 주어지는 상황에서, 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000), 그리고 각 노선의 정보(출발 도시, 도착 도시, 시간 -10,000~10,000)가 주어질 때, 1번 도시에서 출발하여 각 도시로 가는 가장 빠른 시간을 구하는 문제입니다.

음수 가중치가 존재할 수 있으며, 시간을 무한히 오래 전으로 되돌릴 수 있는 경우(음수 사이클)가 있다면 -1을 출력합니다. 도달할 수 없는 도시는 -1을 출력합니다.

접근법

음수 가중치가 있으므로 벨만-포드(Bellman-Ford) 알고리듬을 사용합니다.

벨만-포드 알고리듬은 모든 간선에 대해 거리를 완화하는 작업을 N-1번 반복합니다. 시작 도시의 거리를 0으로, 나머지는 무한대로 초기화한 후, 각 간선 (u, v, w)에 대해 dist[u] + w < dist[v]이면 dist[v]를 갱신합니다.

N-1번의 완화 후에도 거리가 갱신되는 간선이 있다면 음수 사이클이 존재합니다. 이를 확인하기 위해 한 번 더 모든 간선을 순회하여 거리가 줄어드는지 검사합니다.

음수 사이클이 없다면 각 도시까지의 최단 거리를 출력하고, 도달 불가능한 도시는 -1을 출력합니다.

시간 복잡도는 O(N × M)입니다.

---

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class Program {
    const long INF = (long)1e18;

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

      var edges = new List<(int from, int to, int weight)>(m);
      for (var i = 0; i < m; i++) {
        var edge = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
        var from = edge[0];
        var to = edge[1];
        var weight = edge[2];
        edges.Add((from, to, weight));
      }

      var dist = new long[n + 1];
      for (var i = 1; i <= n; i++)
        dist[i] = INF;
      dist[1] = 0;

      for (var i = 1; i <= n - 1; i++) {
        var updated = false;
        foreach (var (from, to, weight) in edges) {
          if (dist[from] == INF) continue;
          var newDist = dist[from] + weight;
          if (newDist < dist[to]) {
            dist[to] = newDist;
            updated = true;
          }
        }
        if (!updated) break;
      }

      foreach (var (from, to, weight) in edges) {
        if (dist[from] == INF) continue;
        if (dist[from] + weight < dist[to]) {
          Console.WriteLine(-1);
          return;
        }
      }

      for (var i = 2; i <= n; i++) {
        Console.WriteLine(dist[i] == INF ? -1 : dist[i]);
      }
    }
  }
}

C++

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

typedef long long ll;
typedef vector<tuple<int, int, int>> vt;

const ll INF = (ll)1e18;

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

  int n, m; cin >> n >> m;
  vt edges;
  edges.reserve(m);
  
  for (int i = 0; i < m; i++) {
    int from, to, weight; cin >> from >> to >> weight;
    edges.push_back({from, to, weight});
  }

  vector<ll> dist(n + 1, INF);
  dist[1] = 0;

  for (int i = 1; i <= n - 1; i++) {
    bool updated = false;
    for (auto [from, to, weight] : edges) {
      if (dist[from] == INF) continue;
      ll newDist = dist[from] + weight;
      if (newDist < dist[to]) {
        dist[to] = newDist;
        updated = true;
      }
    }
    if (!updated) break;
  }

  for (auto [from, to, weight] : edges) {
    if (dist[from] == INF) continue;
    if (dist[from] + weight < dist[to]) {
      cout << -1 << "\n";
      return 0;
    }
  }

  for (int i = 2; i <= n; i++) {
    if (dist[i] == INF) cout << -1 << "\n";
    else cout << dist[i] << "\n";
  }

  return 0;
}