백준 1753: 최단경로

#include <iostream>
#include <vector>
#include <utility> // pair
#include <queue> // pq
#define MAX 20001
#define INF 99999999
using namespace std;

vector< pair<int, int> > graph[MAX]; // graph[from] = <to, weight>, <to, weight>...
vector<int> dist(MAX, INF);

void update(int from, int old, priority_queue< pair<int, int> > * pq) {
	int edge = graph[from].size();
	int i;

	for (i = 0; i < edge; i++) {
		int to = graph[from][i].first;
		int weight = graph[from][i].second;

		int newDist = old + weight;

		if (newDist < dist[to]) {
			dist[to] = newDist;
			pq->push(make_pair(-newDist, to));
		}
	}
}

void dijkstra(int src) {
	priority_queue< pair<int, int> > pq; // (-weight, to)
	dist[src] = 0;

	pq.push({ 0, src });
	while (!pq.empty()) {
		int weight = -pq.top().first;
		int from = pq.top().second;
		pq.pop();

		if (dist[from] < weight) continue;
		else update(from, weight, &pq);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int V, E, src, from, to, weight, i;
	cin >> V >> E;
	cin >> src;

	for (i = 0; i < E; i++) {
		cin >> from >> to >> weight;
		graph[from].push_back(make_pair(to, weight));
	}

	dijkstra(src);

	for (i = 1; i <= V; i++) {
		if (dist[i] == INF) cout << "INF" << "\n";
		else cout << dist[i] << "\n";
	}
	return 0;
}