BOJ - 1753번 최단경로 (C++)

문제 출처: https://www.acmicpc.net/problem/1753

문제 난이도

Gold 5

문제 접근법

다익스트라로 공부해볼겸 먼저 개념을 정리하고 이 문제를 푸는 것을 추천한다.
다익스트라는 start node를 정하고 그 후 모든 정점까지 걸리는 시간을 계산한다.
그렇기 때문에 이 문제에 적합한 알고리즘 기본 풀이법이라고 볼 수 있다!

통과 소스

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

#define INF 987654321

using namespace std;

int dp[20001];

int main() {
	int V, E;
	cin >> V >> E;
	int K;
	cin >> K;
	vector<vector<pair<int, int>>> arr(V + 1);
	for (int i = 0; i < E; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		arr[a].push_back({ b,c });
	}
	for (int i = 1; i <= V; i++) dp[i] = INF;
	dp[K] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push({ 0,K });
	while (!pq.empty()) {
		int node = pq.top().second;
		int val = -pq.top().first;
		pq.pop();
		for (auto x : arr[node]) {
			int next = x.first;
			int nextVal = val + x.second;
			if (dp[next] > nextVal) {
				dp[next] = nextVal;
				pq.push({ -nextVal, next });
			}
		}
	}
	for (int i = 1; i <= V; i++) {
		if (dp[i] == INF) cout << "INF\n";
		else cout << dp[i] << "\n";
	}

	return 0;
}