백준 1753 - 최단경로(C++)

문제

방향그래프와 시작점이 정해지고 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성해야 한다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 <= V <= 20,000, 1 <= E <= 300,000)

 

u와 v는 서로 다르며 w는 10 이하의 자연수이다.

 

서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

 

예제 입력

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

예제 출력

0
2
3
7
INF

문제 해결

어디서 힌트를 얻을 수 있을까?

 

위의 문제에서 정점, 가중치, 방향 그래프, 최단 경로라는 키워드를 볼 수 있다. 이를 통해 이 문제가 그래프 이론을 이용한 문제라는 것을 알 수 있었고, 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 이라는 부분에서 이 문제가 다익스트라 알고리즘의 구현을 보고 싶어한다는 것을 알 수 있었다.

코드

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

int INF = 987654321;
std::vector<std::pair<int, int> > varr[20001];
int dist[20001];

void Dijkstra(int S)
{
	std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > > pq;
	pq.push(std::make_pair(0, S));
	dist[S] = 0;
	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 < varr[here].size(); i++)
		{
			int there = varr[here][i].first;
			int nextDis = cost + varr[here][i].second;
			if (dist[there] > nextDis)
			{
				dist[there] = nextDis;
				pq.push(std::make_pair(nextDis, there));
			}
		}
	}
}


int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int N, E, S;
	std::cin >> N >> E >> S;
	for (int i = 0; i < E; i++)
	{
		int U, V, W;
		std::cin >> U >> V >> W;
		varr[U].push_back(std::make_pair(V, W));
	}
	for (int i = 1; i <= N; i++)
		dist[i] = INF;
	Dijkstra(S);
	for (int i = 1; i <= N; i++)
	{
		if (dist[i] == INF)
			std::cout << "INF" << "\n";
		else
			std::cout << dist[i] << "\n";
	}
	return 0;
}

문제 출처

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

1753번: 최단경로

이론

https://deulee.tistory.com/10

다익스트라(Dijkstra) 알고리즘