1916 - 최소비용 구하기

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

1916번: 최소비용 구하기

N개의 도시가 있고 다른 도시에 도착하는 M개의 버스가 있을 때 A에서 B로 가는 최소비용을 출력하는 문제이다. 

최단경로 알고리즘인 다익스트라를 이용하여 문제를 해결할 수 있다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 0x7fffffff;
using namespace std;
vector<pair<int, int>> adj[1001];
int dist[1001];
bool visited[1001];
// 정점 root에서 end로 가는 최단경로 구하는 함수
void dijkstra(int root, int end) {
	dist[root] = 0;
	priority_queue<pair<int, int>> q;
	//max heap에는 -를 붙여주면 dist의 최소값을 참조할 수 있다.
	q.push({ 0, root });
	while (!q.empty()) {
		int now = q.top().second; q.pop();
		
		if (visited[now]) continue;
		visited[now] = true;
		for (auto p : adj[now]) {
			int next = p.first;
			int w = p.second;
			// w + dist[now] < dist[next] 이면 갱신해준다.
			if (w + dist[now] < dist[next]) {
				dist[next] = w + dist[now];
				// -를 붙여주면 가장 작은 dist가 가장 큰 값이 되어 heap에 들어가므로 
				// logn만에 찾을 수 있다.
				q.push({ -dist[next], next });
			}
		}
	}
	printf("%d", dist[end]);
}

int main()
{
	int N, M;
	cin >> N >> M;
	int s, e;
	// 인접리스트로 저장
	for (int m = 0; m < M; m++) {
		int u, v, x;
		cin >> u >> v >> x;
		adj[u].push_back({ v, x });
	}
	cin >> s >> e;
	// 무한대로 초기화
	for (int i = 1; i <= N; i++) {
		dist[i] = INF;
	}
	dijkstra(s, e);
}