[BOJ] 백준 1753 최단경로

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

이 문제는 최단경로 문제이므로 다익스트라 알고리즘으로 풀면 되는 문제 입니다.
다익스트라 알고리즘이란, 그래프에서 정점과 간선이 있을 때, 시작 정점과 목적지 정점까지의 거리가 시작정점과 경유지 정점과 목적지 정점까지의 거리보다 클 때, 시작정점과 목적지 정점까지의 거리를 후자의 거리로 최신화 시키는 문제 입니다.
 알고리즘을 구현하기 위해 우선순위 큐를 사용하였습니다.
우선순위 큐에는 현재까지 고려된 간선들을 오름차순으로 정렬한 것 입니다.
우선순위 큐의 top을 뽑고, 그 top 정점과 연결된 간선들을 전부 큐에 넣어줍니다.
그 과정에서 거리 최신화를 시켜줍니다.

소스코드 :

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int MAX = 20000 + 1;
const int INF = 987654321;

int V, E, K;

vector > graph[MAX]; // destination, weight;

vector dijkstra(int start, int vertex) {
 vector distance(vertex, INF); // start를 기준으로 거리
 distance[start] = 0; // 자기 자신에게 가는 비용은 0
 priority_queue, vector>, greater>> pq; // Cost, Vertex
 pq.push(make_pair( 0,start )); // 초기 비용과 시작점

 while (!pq.empty()) {
  int cost = pq.top().first;
  int curVertex = pq.top().second;
  pq.pop();

  // 최소거리를 원하므로
  if (distance[curVertex] < cost) {
   continue;
  }
  // neighbour 다 확인
  for (int i = 0; i < graph[curVertex].size(); i++) {
   int neighbor = graph[curVertex][i].first;
   int neighborDistance = cost + graph[curVertex][i].second;

   // 최소 경로 발견시 업데이트
   if (distance[neighbor] > neighborDistance) {
    distance[neighbor] = neighborDistance;
    pq.push(make_pair(neighborDistance, neighbor));
   }
  }
 }
 return distance;
}


int main() {
 cin >> V >> E >> K;
 ios_base::sync_with_stdio(0);
 V++; // 정점번호 1부터 시작
 for (int i = 0; i < E; i++) {
  int source, destination, cost;
  cin >> source >> destination >> cost;

  graph[source].push_back(make_pair(destination, cost));
 }
 vector result = dijkstra(K, V);
 for (int i = 1; i < V; i++) {
  if (result[i] == INF) {
   cout << "INF" << endl;
  }
  else {
   cout << result[i] << endl;
  }
 }
 return 0;
}