최단경로 (feat. 백준, 1753번)

최단경로
https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
int V, E, K;
set<pair<int, int>> arr[20001];
int ans[20001];
void bfs() {
	register int x, y, w1, w2;
	ans[K] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
	q.push(make_pair(0, K));
	while (!q.empty()) {
		auto t = q.top(); q.pop();
		w1 = t.first, x = t.second;
		for (auto iter = arr[x].begin(); iter != arr[x].end(); ++iter) {
			y = iter->first, w2 = iter->second;
			if (ans[y] > w1 + w2)
				ans[y] = w1 + w2, q.push(make_pair(ans[y], y));
		}
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> V >> E >> K;
	for (register int v = 1; v <= V; ++v)
		ans[v] = static_cast<int>(1e9);
	for (register int e = 0, x, y, w; e < E; ++e)
		cin >> x >> y >> w, arr[x].insert(make_pair(y, w));
	bfs();
	for (register int i = 1; i <= V; ++i)
		if (ans[i] == static_cast<int>(1e9))
			cout << "INF" << "\n";
		else
			cout << ans[i] << "\n";
	return 0;
}
// *&)*@*

1. 가중치의 의미는 값을 의미합니다. 즉 1(정점) 2(정점) 2(가중치) 의 의미는 1에서 2로 갈때 2만큼 걸린다 라는 의미입니다.
2. 각 노드의 가중치를 출력하는 문제입니다. 즉, 다른 (정점, 정점, 가중치) 에 의해 기존 노드의 가중치의 값이 달라질 수 있음을 의미합니다. (더 낮은 가중치로)
3. 저는 bfs 함수의 q 변수를 (가중치, 노드) 에 대해 오름차순으로 정렬된 우선순위큐로 사용했습니다.
4. 왜냐하면 낮은 가중치부터 계산하게 되면 이후 동일한 노드 y에 대해서 ans[y] > w1 + w2 의 조건이 성립되지 않으므로 우선순위큐에 push가 일어나지 않게 되고, 그로 인해 빠른 결과 도출이 가능하기 때문입니다. (동일 노드 y에 대해 낮은 가중치부터 계산되었으므로 더 높은 가중치는 무시되는 효과입니다.)