백준 1753: 최단경로

문제 요약

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

문제 분류

• 그래프 이론
• 데이크스트라
• 최단 경로

문제 풀이

각 가중치가 자연수이므로 다익스트라 알고리즘을 이용하여 풀 수 있다. 각 가중치는 pair<int,int>인 vector로 주어서 u에서 v로 w의 가중치의 간선이 주어진다면, weight[u]에 {v, w}의 pair를 저장한다. 즉 weight[u]에는 u에서 출발하는 간선들이 줄줄이 vector로 이어져 있을 것이다. 가중치까지 표현하기 위해 pair<int, int>로 second에 가중치를 저장하였다.

초기 결과값은 모두 INF로 초기화, 우선순위 큐로 해결하였다. 다음 방문할 정점을 최소 힙, 우선순위 큐에서 찾는 것이다. 우선순위 큐는 pair<int, int>로, first는 가중치, second는 진입 정점으로 두어서 가중치를 기준으로 정렬시켜서, 다음에 방문할 정점을 선택한다. 현재 방문한 정점을 통해 최단 경로가 갱신되었다면, 해당 정점도 재방문해야하므로 우선순위 큐에 push해준다. 더이상 방문할 정점이 없을 때까지 반복. 마지막은 역시 INF값만 "INF"를 출력해주고, 나머지는 최단경로를 그대로 출력한다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 1000000

using namespace std;

vector<pair<int,int>> weight[20000];
int res[20000];

int main()
{
	int v, e, k, in1, in2, in3;
	priority_queue<pair<int, int>, vector<pair<int,int>>, greater<>> pq;
	scanf("%d%d", &v, &e);
	scanf("%d", &k);
	k--;
	for (int i = 0; i < v; i++)
		res[i] = INF;
	for (int i = 0; i < e; i++) {
		scanf("%d%d%d", &in1, &in2, &in3);
		weight[in1 - 1].push_back({ in2 - 1,in3 });
	}
	res[k] = 0;
	pq.push({ 0, k });

	while (!pq.empty()) {
		auto t = pq.top();
		pq.pop();
		for (auto& it : weight[t.second]) {
			if (res[it.first] > res[t.second] + it.second) {
				res[it.first] = res[t.second] + it.second;
				pq.push({ res[it.first], it.first });
			}
		}
	}
	for (int i = 0; i < v; i++) {
		if (res[i] == INF) printf("INF\n");
		else printf("%d\n", res[i]);
	}
	return 0;
}