[백준] 1753번 최단경로

1753번: 최단경로

#include <iostream> 
#include <vector> 
#include <queue> 
#include <algorithm>
using namespace std;
vector<pair<int, int>> adj[20002];
int length[20002];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; //비용 적은 것이 우선이 되게 오름차순 정렬
bool visited[20002];

int main() {
	int numOfVertex, numOfEdge, startNode;
	cin >> numOfVertex >> numOfEdge >> startNode;
	const int INF = 2147483647;
	int from, to, weight;
	for (int i = 0; i < numOfEdge; i++) {
		cin >> from >> to >> weight;
		adj[from].push_back(pair<int, int>(weight, to)); //pair의 앞쪽에 있는 숫자를 기준으로 오름차순 정렬하므로 가중치를 앞에 둔다.
	}
	for (int i = 1; i <= numOfVertex; i++) {
		length[i] = INF;
	}
	length[startNode] = 0; //나에서 나로 가는 최단경로는 0
	q.push(make_pair(0, startNode));
	while (!q.empty()) {
		int cost = q.top().first;
		int now = q.top().second;
		q.pop();
		if (length[now] < cost || visited[now]) continue;
		visited[now] = true;
		for (int i = 0; i < adj[now].size(); i++) {
			if (length[adj[now][i].second] > adj[now][i].first + cost) {
				q.push(make_pair(adj[now][i].first + cost, adj[now][i].second));
				length[adj[now][i].second] = adj[now][i].first + cost;
			}
		}
	}
	for (int i = 1; i <= numOfVertex; i++) {
		if (length[i] >= INF) cout <<"INF\n";
		else cout << length[i] << '\n';
	}
	return 0;
}