백준/1753/Dijkstra/최단경로

백준/1753/Dijkstra/최단경로
시작점으로 부터의 다른 정점에 최단거리를 재기 위한 문제로 Dijkstra 알고리즘을 사용하였습니다.

해당 그림은 예제를 이용하여 만든 표로 Dijkstra 알고리즘을 그림으로 표현하자면

우선 시작 지점인 정점 1에서 시작합니다. 정점1에서 정점1로 가는법은 그대로 있으면 되니 0을 넣어주고 다음으로 1에서 갈 수 있는 정점들의 거리를 기록합니다.

그 다음으로는 정점2로 가는 최단거리가 가장 짧으니 2를 fix하고 2에서 갈 수 있는 정점들의 최단 거리를 기록합니다.

다음으로는 정점 3로 가는 최단 거리가 가장 짧으니 3을 fix하고 3에서 갈 수 있는 정점들의 최단 거리를 기록합니다.

마지막으로 정점 4로 가는 최단 거리가 가장 짧으니 4를 fix하고 1에서 5로 갈 수 있는 선은 없으니 INF를 기록합니다.

이 처럼 시작 지점으로 부터 가장 짧은 거리가 fix되면 해당 정점으로 부터 뻗어지는 길에 최단거리를 기록하는 방식으로 시작지점으로 부터 정점들의 최단거리를 기록합니다.

이를 위해 우선순위 큐를 사용하여 아래와 같이 표현합니다.

void solve()
{
	dist[st] = 0;
	pq.push({ 0,st });
	while (!pq.empty())
	{
		auto cur = pq.top(); pq.pop();
		if (dist[cur.second] != cur.first)continue;
		for (auto nxt : adj[cur.second])
		{
			if (dist[nxt.second] <=dist[cur.second]+nxt.first )continue;
			dist[nxt.second] = dist[cur.second] + nxt.first;
			pq.push({ dist[nxt.second],nxt.second });
		}
	}
	solution();
}

풀이

1. 첫번째 풀이

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

void solve();
void solution();

int V, E, st;
vector<pair<int, int>> adj[20005];
int dist[20005];
int INF = 0x3f3f3f3f;

priority_queue < pair<int, int>,
	vector <pair<int, int>>,
	greater<pair<int, int>>> pq;


void solve()
{
	dist[st] = 0;
	pq.push({ 0,st });
	while (!pq.empty())
	{
		auto cur = pq.top(); pq.pop();
		if (dist[cur.second] != cur.first)continue;
		for (auto nxt : adj[cur.second])
		{
			if (dist[nxt.second] <=dist[cur.second]+nxt.first )continue;
			dist[nxt.second] = dist[cur.second] + nxt.first;
			pq.push({ dist[nxt.second],nxt.second });
		}
	}

	solution();
}

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

int main()
{
	cin >> V >> E >> st;
	for (int i = 0; i < E; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({ w,v });
	}
	fill(dist, dist + V+1, INF);

	solve();
}