[백준] 1916번. 최소비용 구하기 (C++)

문제

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

---

풀이

[다익스트라]

https://yun000.tistory.com/148

다익스트라 알고리즘 (Dijkstra)

 

+) 주의!! 방향 그래프이다!!! 무방향 그래프로 생각해서 한참 헤맸다.

---

코드

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

typedef pair<int, int> p;

int main() {

	//INPUT///////////////////////////////////////////////////
	int N, M; cin >> N >> M;
	
	//start에서 특정 node로 이동하기 위해 필요한 비용
	vector<int>prices(N + 1, numeric_limits<int>::max());
	
	//graph(방향 그래프!!!)
	vector<vector<p>>graph(N + 1);
	int from, to, price;
	for (int i = 0; i < M; i++) {
		cin >> from >> to >> price;
		graph[from].push_back({ to,price });//node, price
	}
	
	//출발지, 도착지
	int start, destination;
	cin >> start >> destination;



	//CALCULATE///////////////////////////////////////////////
	prices[start] = 0;
	priority_queue<p, vector<p>, greater<p>>pq;
	pq.push({ 0,start });

	while (!pq.empty()) {
		int node = pq.top().second;//현재 node
		int nowPrice = pq.top().first;//start에서 현재노드까지 거리
		pq.pop();

		if (prices[node] < nowPrice) continue;

		for (int i = 0; i < graph[node].size(); i++) {

			int next = graph[node][i].first;//연결된 노드
			int price = graph[node][i].second;//현재 노드에서 연결된 노드까지 비용
			
			if (prices[next]> price + nowPrice) {
				prices[next] = price + nowPrice;
				pq.push({ prices[next],next });
			}
		}
	}
	
	cout << prices[destination];

}