[Gold 4] 1753 최단 경로

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

1753번: 최단경로

 

이 문제는 다익스트라 알고리즘을 활용해야한다.

노드간의 이동 방법과 가중치를 입력 받기 때문에 일반적인 다익스트라 알고리즘을 사용하면 된다.

 

출력 시 INF인 경우 INF를 출력하도록 출력만 신경쓰면 된다.

 

#include<iostream>
#include <vector>
#include <queue>

using namespace std;

#define INF 100000000

int V, E;
int dist[20001];
vector<pair<int, int>> nodes[20001];

void dijkstra(int start) {
	priority_queue<pair<int, int>> pq;

	pq.push({ 0,start });
	dist[start] = 0;

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

		if (dist[here] < cost) continue;

		for (int i = 0; i < nodes[here].size(); i++) {
			int vist_cost = cost + nodes[here][i].first;

			if (vist_cost < dist[nodes[here][i].second]) {
				dist[nodes[here][i].second] = vist_cost;
				pq.push({ -vist_cost,nodes[here][i].second });
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> V >> E;

	for (int i = 1; i <= V; i++)
		dist[i] = INF;

	int start;
	cin >> start;

	int u, v, w;
	for (int i = 0; i < E; i++) {
		cin >> u >> v >> w;
		nodes[u].push_back({ w,v });
	}

	dijkstra(start);

	int count = 0;
	for (int i = 1; i <= V; i++) {
		if (dist[i] == INF) {
			cout << "INF" << '\n';
			continue;
		}
		cout << dist[i] << '\n';
	}

	return 0;
}