백준 1916 최소비용 구하기

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 출발 도시에서 도착 도시까지 걸리는 최소비용을 구하는 문제입니다.

 

따라서 다익스트라 알고리즘을 통하여 구하여야 합니다.  다익스트라 알고리즘이란 우선순위 큐를 사용하여 이동 할 수 있는 정점중 가장 가중치가 적은 경로로 이동하면서 그 정점으로 이동하는데 지금의 비용과 기존에 저장되어 있는 비용중 더작은 비용을 저장하면서 각각의 정점으로 이동하는데의 최소비용을 구하는 알고리즘입니다. 

 

#include <iostream>
#include <vector>
#include <queue>

#define P pair<int,int>
#define inf 100000001
using namespace std;

priority_queue<int , vector<int>, greater<int>> pq;
vector<P> v[1001];
int weight[1001];

void Dijkstra(int start) {
	
	pq.push(start);
	weight[start] = 0; 
	while(!pq.empty()) {
		int num = pq.top();
		pq.pop();
		for(int i = 0; i < v[num].size(); i++) {
			
			if(weight[num] + v[num][i].first < weight[v[num][i].second]) {
				weight[v[num][i].second] = weight[num] + v[num][i].first;
				pq.push(v[num][i].second);
			}
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N,M;
	cin >> N >> M;
	fill_n(weight, 1001, inf);
	for(int i = 0; i < M; i++) {
		int a,b,c;
		cin >> a >> b >> c;
		v[a].push_back(make_pair(c, b));
	}
	int start, arrive;
	cin >> start >> arrive;
	Dijkstra(start);
	cout<<weight[arrive];
	
	return 0;
}