[백준] 1504 특정한 최단 경로 - C++

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

---

다익스트라를 사용하는 최단거리 문제지만,

특정 두 노드를 경유해야한다는게 관건이다.

경유하면서 거리를 최단으로 줄이는 방법을 생각해보면 도움이 된다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int INF = 1e8; //<1>
int N, E;
vector<pair<int, int>> graph[801];
vector<int> dist;
void daik(int start) {
	dist.assign(N + 1, INF);
	dist[start] = 0;
	priority_queue <pair<int, int>, vector<pair<int, int>>, greater<>> pq;
	pq.push({ 0, start });
	while (!pq.empty()) {
		auto [cur_dist, cur] = pq.top();
		pq.pop();
		if (dist[cur] < cur_dist) {
			continue;
		}
		for (auto [next, cost] : graph[cur]) {
			if (dist[next] > cur_dist + cost) {
				dist[next] = cur_dist + cost;
				pq.push({ dist[next], next });
			}
		}
	}
}
int main() {
	cin >> N >> E;
	for (int i = 0; i < E; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		graph[u].push_back({ v, w });
		graph[v].push_back({ u, w }); //<2>
	}
	int a, b;
	cin >> a >> b;
	//<3>
	daik(a); //<3-1>
	int a_1 = dist[1];
	int a_b = dist[b];
	int a_n = dist[N];
	daik(b); //<3-2>
	int b_1 = dist[1];
	int b_n = dist[N];
	//<4>
	int route_1 = a_1 + a_b + b_n;
	int route_2 = b_1 + a_b + a_n;

	int result = min(route_1, route_2);
	if (result >= INF) {
		result = -1;
	}
	cout << result;
	return 0;
}

daik함수는 이전 글들에서 사용했던 daik함수와 별 다른점이 없다,

<1>에서 INF값으로 기존 사용하던 1e9가 아니라 1e8을 사용했는데, 뒤에서 자세히 설명하겠다.

문제에서 주어지는 그래프는 양방향이므로 <2>를 통해 양방향으로 저장해준다.

 

경유지를 경유했을때의 최단거리는,

(시작지~경유지의 최단거리) + (경유지~목적지의 최단거리) 일것이다.

<3-1>부분을 보면 a로 다익스트라를 돌린다. 이 말은 즉슨

a와 다른 모든노드들간의 최단거리가 dist에 저장되게 한다는것이다.

그러니 일단 시작지~a경유지, a경유지~b경유지, a경유지~목적지의 최단거리를 각각 저장해준다.

경유지가 두곳이기 때문에 <3-2>부분을 통해 b에 대한 최단거리도 저장한다. (a~b는 이미 구했으니 저장 안해도 됨)

 

<4> : 위에서 구한 각각의 경로들을 더해 route1, 2에 저장해준다.

이때!!!!!!!!!! <1>에서 왜 INF를 1e8로 저장했는지 설명하겠다!!!!!!!

부분경로 3개를 더하는 과정에서, 만약 세 경로 모두 모종의 이유(도달하지 못한다거나..)로 INF값을 가진다면,

route를 정하는 식이 INF+INF+INF가 되고!!

INF가 1e9였다면 int범위(약 2e9)를 초과해 오버플로우가 난다!!

따라서 1e8정도로 해준것이다..

 

그 후 위에서 계산한 각각 다른 두 경로 중 더 짧은 경로를 출력하면 된다.

---

정말 재밌는거 같다..

다익스트라를 어느정도 하게 되면

다른 최단거리 알고리즘도 공부해야겠다.

---