코딩하는 두꺼비

www.acmicpc.net/problem/1916

그냥 단순한 다익스트라 알고리즘을 사용한 문제였다.

최근 본 코테에서 다익스트라가 나왔는데도 불구하고 생각이 안나 못풀었던 걸 생각하면ㅠㅠ 미리 왜 공부를 안했나 후회가 되는 문제였다.

참고 블로그: alswnsdl.tistory.com/13

이 블로그를 통해 우선순위를 이용한 다익스트라 알고리즘을 공부하였고 문제에 적용할 수 있었다.

#define _CRT_SECURE_NO_WARNINGS
#define INF 1e9
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
	int V, E, start, end;
	int a, b, c;
	cin >> V >> E;
	vector<pair<int, int>> arr[1001];
	int dist[1001];

	for (int i = 0; i < E; i++) {
		cin >> a >> b >> c;
		arr[a].push_back({ b,c });
	}
	cin >> start >> end;
	fill(dist, dist + V + 1, INF);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

	pq.push({ 0, start});
	dist[start] = 0;

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

		for (int i = 0; i < arr[here].size(); i++) {
			int next = arr[here][i].first;
			int ncost = arr[here][i].second;

			if (dist[next] > dist[here] + ncost) {
				dist[next] = dist[here] + ncost;
				pq.push({ dist[next], next });
			}
		}
	}
	cout << dist[end];
	return 0;
}