[BOJ] 백준 1916 최소비용 구하기

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

이 문제는 다익스트라 알고리즘을 사용하여, 최소비용을 구해야 하는 문제 입니다.
다익스트라 알고리즘은
1. 최소 우선순위 큐
2. 시점에서부터의 Cost를 저장할 distance 리스트
3. 각 그래프의 연결 관계를 저장할 Pair(int, int) 그래프가 필요 합니다.

접근 방식으로는,
1. 각 점의 연결 관계(시점, 종점)와 weight를 graph에 저장합니다.
2. 다익스트라 함수에 시점과 정점의 개수를 매개변수로 주고, 실행시킵니다.
- 함수 내에서 우선, 시점과 그 가중치인 0을 pq에 넣습니다.
- pq가 비어있지 않을경우 돌아가는 루프 안에 pq.top.first(cost) 와 pq.top.second(current vertex)를 따로 변수에 저장합니다.
- 만약 cost가 distance(currentVertex)보다 작다면 패스 합니다
- 그 외, graph[curVertex].size만큼 도는 루프를 작성 합니다.
- 루프 안에서 만약 distance[graph[curVertex][i].first] > graph[curVertex][i].second + cost 라면 distance를 후자의 값으로 최신화 시킵니다. 그 후 pq에 최신화 시킨 값을 넣습니다.
3. 다익스트라 함수 종료 입니다. 종료 한다면 distance에는 최신화 된 값이 남아 있습니다.

소스코드 :

#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;
 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));
 }
 int destination;
 cin >> K >> destination;
 vector result = dijkstra(K, V);
 //sort(result.begin(), result.end());
 cout << result[destination];
 //return 0;
}