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

다익스트라 문제

기록용

 

#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;
}