[백준 11779] 최소비용 구하기 2 (C#, C++) - soo:bak

문제 링크

11779번 - 최소비용 구하기 2

설명

시작 도시에서 도착 도시까지 가는 최소 비용과 그 경로를 구하는 문제입니다. 버스 노선마다 비용이 다르고, 한 도시에서 다른 도시로 가는 버스가 여러 개 있을 수 있습니다.

접근법

먼저 다익스트라 알고리즘으로 시작 도시에서 도착 도시까지의 최단 비용을 구합니다. 시작 도시의 비용은 0, 나머지는 무한대로 초기화한 뒤 우선순위 큐를 이용해 비용이 작은 도시부터 처리합니다. 현재 도시를 경유하는 것이 더 저렴하면 해당 도시의 비용을 갱신하고 큐에 추가합니다.

다음으로 경로를 복원하기 위해 비용이 갱신될 때마다 이전 도시를 기록합니다. 예를 들어 도시 3에서 도시 5로 갈 때 비용이 갱신되었다면, 도시 5의 이전 도시로 3을 저장합니다.

이후 도착 도시에서 시작해 기록된 이전 도시를 따라가면 경로를 역순으로 얻을 수 있습니다. 이를 뒤집어 출력하면 시작 도시부터 도착 도시까지의 경로가 됩니다.

---

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var m = int.Parse(Console.ReadLine()!);

      var adj = new List<(int to, int w)>[n + 1];
      for (var i = 1; i <= n; i++)
        adj[i] = new List<(int, int)>();

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

      var se = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      var start = se[0];
      var end = se[1];

      const int INF = int.MaxValue;
      var dist = new int[n + 1];
      var prev = new int[n + 1];
      Array.Fill(dist, INF);

      var pq = new PriorityQueue<int, int>();
      dist[start] = 0;
      pq.Enqueue(start, 0);

      while (pq.Count > 0) {
        pq.TryDequeue(out var cur, out var curCost);
        if (curCost > dist[cur])
          continue;
        foreach (var edge in adj[cur]) {
          var nxt = edge.to;
          var w = edge.w;
          var nd = dist[cur] + w;
          if (nd < dist[nxt]) {
            dist[nxt] = nd;
            prev[nxt] = cur;
            pq.Enqueue(nxt, nd);
          }
        }
      }

      Console.WriteLine(dist[end]);

      var path = new Stack<int>();
      for (var v = end; v != 0; v = prev[v])
        path.Push(v);
      Console.WriteLine(path.Count);
      Console.WriteLine(string.Join(" ", path));
    }
  }
}

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;

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

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

  vi dist(n + 1, INF);
  vi prev(n + 1, 0);
  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] : adj[u]) {
      int nd = dist[u] + w;
      if (nd < dist[v]) {
        dist[v] = nd;
        prev[v] = u;
        pq.push({nd, v});
      }
    }
  }

  cout << dist[goal] << "\n";

  vi path;
  for (int v = goal; v != 0; v = prev[v])
    path.push_back(v);
  reverse(path.begin(), path.end());
  cout << path.size() << "\n";
  for (int i = 0; i < (int)path.size(); i++)
    cout << path[i] << (i + 1 == (int)path.size() ? '\n' : ' ');

  return 0;
}