백준 14284 간선 이어가기 2

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

#include <iostream>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;


int N, M;
int S, T;
vector<pair<int, int>> v[5001];
int dist[5001];
void input(){
  cin >> N >> M;
  for(int i = 0; i < M; i++){
    int a, b, c;
    cin >> a >> b >> c;
    v[a].push_back({b, c});
    v[b].push_back({a, c});
    
  }
  cin >> S >> T;
}

void dijkstra(int start){
  for(int i = 0; i <= N; i++){
    dist[i] = INF;
  }
  dist[start] = 0;
  priority_queue<pair<int, int>, vector<pair<int, int>>,
                 greater<pair<int, int>>>      pq;
  pq.push({0, start});
  while(!pq.empty()){
    int cost = pq.top().first;
    int node = pq.top().second;
    pq.pop();

    for(int i = 0; i < v[node].size(); i++){
      int nextCost = v[node][i].second;
      int nextNode = v[node][i].first;

      if (cost + nextCost < dist[nextNode]){
        dist[nextNode] = cost + nextCost;

        pq.push({dist[nextNode], nextNode});
      }
    }
  }
}

void solve(){
  input();
  dijkstra(S);
  cout << dist[T];
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  solve();
  return 0;
}