1753 ์ตœ๋‹จ๊ฒฝ๋กœ

์•Œ๊ณ ๋ฆฌ์ฆ˜

1. ๋‹ค์ต์ŠคํŠธ๋ผ

์ฝ”๋“œ

#include <iostream>
#include <queue>
#include <vector>
#define INF 2000000000;
using namespace std;
 
int V, E, s, length[20001];
vector<pair<int, int>> node[20001];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
bool check[20001];
 
void dijkstra();
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> V >> E >> s;
 
	for (int i = 0; i < E; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		node[a].push_back({ b, c });
	}
 
	for (int i = 1; i <= V; i++)
		length[i] = INF;
 
	length[s] = 0;
 
	dijkstra();
 
	for (int i = 1; i <= V; i++) {
		if (length[i] != 2000000000)
			cout << length[i] << '\n';
		else
			cout << "INF\n";
	}
}
 
void dijkstra() {
	q.push({ 0, s });
 
	while (!q.empty()) {
		int d = q.top().first, cur = q.top().second;
		q.pop();
 
		if (d > length[cur] || check[cur])
			continue;
 
		for (int i = 0; i < node[cur].size(); i++) {
			int next = node[cur][i].first, nd = d + node[cur][i].second;
			if (nd < length[next]) {
				q.push({ nd, next });
				length[next] = nd;
			}
		}
		check[cur] = true;
	}
}