[백준] 1753 최단경로

[백준] 1753 최단경로

• https://www.acmicpc.net/problem/1753

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_COST = 987654321;
const int MAX_V = 20000;

int V;
//<u, <v, w>>
vector <pair<int, int>> adj[MAX_V];

//시작 지점에서 각 지점까지의 최소 비용
vector<int> dist(MAX_V, MAX_COST);

void priority_queue_dijkstra(int start) {

	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, start));
	dist[start] = 0;

	while (!pq.empty()) {
		int curNode = pq.top().second;
		int curW = -pq.top().first;
		pq.pop();

		for (int i = 0; i < adj[curNode].size(); i++) {
			int adj_v = adj[curNode][i].first;
			int& adj_w = adj[curNode][i].second;

			if (dist[adj_v] > curW + adj_w) {
				dist[adj_v] = curW + adj_w;
				pq.push({ -dist[adj_v], adj_v });
			}
		}
	}
}

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

	int E, K;
	cin >> V >> E >> K;
	K--;

	//간선 입력받기
	for (int i = 0; i < E; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		u--;
		v--;

		//방향 그래프
		//서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음
		bool replaced = false;
		for (int j = 0; j < adj[u].size(); ++j) {
			int adj_v = adj[u][j].first;
			int& adj_w = adj[u][j].second;
			if (adj_v == v) {
				replaced = true;
				adj_w = min(adj_w, w);
			}
		}
		if (!replaced) {
			adj[u].push_back({ v, w });
		}
	}

	priority_queue_dijkstra(K);
	for (int i = 0; i < V; ++i) {
		if (dist[i] == MAX_COST) cout << "INF\n";
		else cout << dist[i] << "\n";
	}

	return 0;
}