[백준 14284번] 간선 이어가기 2 (C++)

문제링크 : https://www.acmicpc.net/problem/14284

14284번: 간선 이어가기 2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

vector<pii> v[5001];
int dist[5001];
int N, M, a, b, c, s, t;

void dijkstra()
{
   priority_queue<pii, vector<pii >, greater<pii > > pq; //값이 작을수록 우선순위를 가짐
   pq.push({0, s}); //위치와 비용
   dist[s] = 0; //시작점

   while(!pq.empty())
   {
      auto [cost, cur] = pq.top(); pq.pop();

      if(cost > dist[cur]) continue;

      if(cur == t) //s와 t가 연결되는 시점의 최소비용
      {
         cout << cost; 
         return; 
      }

      for(int i=0; i<v[cur].size(); i++)
      {
         int next = v[cur][i].first; //다음 위치
         int ncost = cost + v[cur][i].second; //다음 비용

         if(ncost < dist[next]) //비용갱신
         {
            dist[next] = ncost;
            pq.push({ncost, next});
         }
      }
   }
}
int main() 
{
   ios_base::sync_with_stdio(false); 
   cin.tie(0);

   cin >> N >> M;
   for(int i=0; i<M; i++)
   { 
      cin >> a >> b >> c;
      v[a].push_back({b, c}); //무방향 그래프 (간선, 가중치)
      v[b].push_back({a, c});
   }
   cin >> s >> t;

   for(int i=1; i<=N; i++)
   {
      dist[i] = MAX;
   }

   dijkstra();

   return 0;
}

전형적인 다익스트라 알고리즘 문제이다.

 

해당 문제에서 s와 t가 만나는 시점에서 해당 시점까지의 최소 비용을 구하는 것이므로,

s와 t가 만날 때 다익스트라 알고리즘을 종료하고 현재 위치의 비용을 출력하면 된다.