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

문제 링크

1916번 - 최소비용 구하기

설명

도시와 버스 노선 정보가 주어지는 상황에서, 도시의 개수 N (1 ≤ N ≤ 1,000), 버스의 개수 M (1 ≤ M ≤ 100,000), 각 버스 노선의 정보(출발 도시, 도착 도시, 비용), 그리고 출발점 A와 도착점 B가 주어질 때, A에서 B까지 가는 데 드는 최소 비용을 구하는 문제입니다.

모든 비용은 0 이상이므로 다익스트라(Dijkstra) 알고리듬을 사용할 수 있습니다.

접근법

다익스트라 알고리듬을 사용하여 출발점에서 도착점까지의 최단 경로를 찾습니다.

인접 리스트를 사용하여 각 도시에서 갈 수 있는 도시와 비용을 저장합니다. 우선순위 큐를 사용하여 현재까지 발견한 가장 짧은 거리부터 처리합니다.

출발점의 거리를 0으로, 나머지는 무한대로 초기화한 후, 우선순위 큐에서 거리가 가장 짧은 도시를 꺼내 인접한 도시들의 거리를 갱신합니다. 이미 확정된 거리보다 큰 값은 건너뜁니다.

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

---

Code

C#

using System;
using System.Collections.Generic;

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

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

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

      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 cost = edge[2];
        graph[from].Add((to, cost));
      }

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

      var dist = new int[n + 1];
      Array.Fill(dist, INF);
      dist[start] = 0;
      
      var pq = new PriorityQueue<(int node, int distance), int>();
      pq.Enqueue((start, 0), 0);

      while (pq.Count > 0) {
        var (node, distance) = pq.Dequeue();
        if (distance > dist[node]) continue;
        
        foreach (var (nextNode, cost) in graph[node]) {
          var newDist = distance + cost;
          if (newDist < dist[nextNode]) {
            dist[nextNode] = newDist;
            pq.Enqueue((nextNode, newDist), newDist);
          }
        }
      }

      Console.WriteLine(dist[end]);
    }
  }
}

C++

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

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

const int INF = 987654321;

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

  int n, m; cin >> n >> m;
  vvp graph(n + 1);
  
  for (int i = 0; i < m; i++) {
    int from, to, cost;
    cin >> from >> to >> cost;
    graph[from].push_back({to, cost});
  }
  
  int start, end; cin >> start >> end;

  vector<int> dist(n + 1, INF);
  vector<bool> visited(n + 1, false);
  priority_queue<pii, vector<pii>, greater<pii>> pq;

  dist[start] = 0;
  pq.push({0, start});
  
  while (!pq.empty()) {
    auto [distance, node] = pq.top();
    pq.pop();
    
    if (visited[node]) continue;
    visited[node] = true;
    
    for (auto [nextNode, cost] : graph[node]) {
      if (dist[nextNode] > distance + cost) {
        dist[nextNode] = distance + cost;
        pq.push({dist[nextNode], nextNode});
      }
    }
  }

  cout << dist[end] << "\n";
  
  return 0;
}