[백준 / BOJ] C++ 5972 택배 배송

5972번: 택배 배송

 

문제

https://www.acmicpc.net/problem/5972

5972번: 택배 배송

 

 

풀이

양방향 그래프에서의 다익스트라 알고리즘을 사용하면 풀 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자.

[다익스트라 알고리즘 알아보기]

 

 

코드

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

#define INF 2147483647

int N, M;
vector<pair<int, int>> graph[50001];
vector<int> dist(50001, INF), visited(50001, 0);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

int dijkstra(int s, int e) {
  dist[s] = 0;
  pq.push({0, s});
  while (!pq.empty()) {
    int curr;
    do {
      curr = pq.top().second;
      pq.pop();
    } while (!pq.empty() && visited[curr]);
    if (visited[curr])
      break;
    visited[curr] = 1;
    for (auto &p : graph[curr]) {
      int next = p.first, d = p.second;
      if (dist[next] > dist[curr] + d) {
        dist[next] = dist[curr] + d;
        pq.push({dist[next], next});
      }
    }
  }
  return dist[e];
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> N >> M;
  while (M--) {
    int u, v, w;
    cin >> u >> v >> w;
    graph[u].push_back({v, w});
    graph[v].push_back({u, w});
  }
  cout << dijkstra(1, N);
  return 0;
}