[C++] 백준 1753번 - 최단 경로

처음으로 다익스트라 문제를 풀어보았다.

학교에서 이제 막 다익스트라의 수도코드를 공부했는데, 실제로 구현해보니 너무 어려웠다.

 

특이하게 다익스트라는 1:1의 경로를 알기 위해서 1:N의 경로를 전부 구해야 문제를 해결할 수 있다는 점이었다.

어째뜬 문제에서 요구하는 것이 1:N의 경로를 요구하는 것이었기때문에 크게 문제가 되지는 않았다. 

 

동아리에서 다익스트라에서 배울때는 변수 이름들을 u, v 등 vertex를 만들때 기본적으로 활용되는 이름들을 썼었는데,

이렇게 코드를 작성하다보니까 직관적으로 다가오지 않아서 변수 이름들을 좀 명확하게 써놓았다.

다익스트라에 좀 익숙해지면 변수명도 교체해야하지 않을까 싶다. 

#include <bits/stdc++.h>
#define endl '\n'
#define INF 987654321
#define pii pair<int, int>
using namespace std;
int V, E, start;

vector<pii> graph[20010];
int dist[20010] = { 0, };
priority_queue<pii, vector<pii>, greater<pii>> pq;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> V >> E;
	cin >> start;

	for (int i = 0; i < E; i++) {
		int u, v, w; cin >> u >> v >> w;
		graph[u].push_back({ w, v });
	}

	for (int i = 1; i < V + 1; i++) 
		dist[i] = INF;

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

	while (!pq.empty()) {
		int distance = pq.top().first;
		int current_vertex = pq.top().second;
		pq.pop();

		if (dist[current_vertex] < distance) continue;

		for (int i = 0; i < graph[current_vertex].size(); i++) {
			int next_vertex = graph[current_vertex][i].second;
			int next_weight = graph[current_vertex][i].first;

			if (distance + next_weight < dist[next_vertex]) {
				dist[next_vertex] = distance + next_weight;
				pq.push({ dist[next_vertex], next_vertex });
			}
		}
	}

	for (int i = 1; i < V + 1; i++) {
		if (dist[i] == INF) cout << "INF" << endl;
		else cout << dist[i] << endl;
	}

	return 0;
}