백준 1753번: 최단경로

[문제 링크]

1753번: 최단경로

---

한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 다익스트라 알고리즘을 이용하면 쉽게 풀 수 있는 문제였다.

---

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

const int INF = 987654321;
int V, E;
vector<pair<int, int>> adj[20001];

vector<int> dijkstra(int start)
{
	vector<int> dist(V+1, INF);
	dist[start] = 0;

	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });

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

		if (dist[here] < cost) continue;
		
		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].first;
			int nextDist = cost + adj[here][i].second;

			if (dist[there] > nextDist)
			{
				dist[there] = nextDist;
				pq.push({ -nextDist, there });
			}
		}
	}

	return dist;
}

int main(void)
{
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	cin >> V >> E;

	int start;
	cin >> start;

	for (int i = 0; i < E; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;

		adj[u].push_back({ v,w });
	}

	vector<int> result = dijkstra(start);

	for (int i = 1; i <= V; i++)
	{
		if (result[i] == INF)
			cout << "INF" << '\n';
		else
			cout << result[i] << '\n';
	}

	return 0;
}

알고리즘 200일 프로젝트 - 163 day