백준 1504번

백준 1504번 (특정한 최단 경로)

이 문제는 방향성이 없는 그래프가 먼저 주어지고, 해당 그래프에서 1 -> N까지의 최단 경로를 구하는 문제이다. 이 때 조건이 주어지는데 문제에서 주어진 2개의 정점을 반드시 경로에 포함시켜야한다.

해당 문제는 쉽게 해결하는 방식은 쉽게 생각해내었지만 중간 계산에서의 overflow를 고려하지 못해서 골치가 좀 아팠던 문제였다. 사실 2개의 정점을 반드시 지나는 최단경로는 결과가 2가지 밖에 나올 수 없다. 예를 들어, 1에서 N까지 최단 경로를 구해야하는데 V1, V2를 모두 포함시켜야한다고 가정해보자. 이 때, 나올 수 있는 경우는 2가지 뿐이다.

1. 1 -> V1 -> V2 -> N
2. 1 -> V2 -> V1 -> N

물론 이 화살표 안에 여러 정점들을 거쳐갈 수 있겠지만 사실 큰 틀은 이렇게 두 가지 뿐이다. 따라서 다익스트라 알고리즘을 3번 적용하여 특정한 경로의 최단 거리만 구한 뒤, 비교를 통하여 1번의 경우와 2번의 경우 중 더 짧은 거리를 구하여 정답을 출력하면 된다.

#include <bits/stdc++.h>

using namespace std;

struct EDGE {
	int to, w;
};

vector<EDGE> v[805];
vector<int> res;
const int INF = 1e9;
int chk[805];
int n, e;

bool operator < (EDGE e1, EDGE e2) {
	return e1.w > e2.w;
}

void func(int s) {
	fill(res.begin(), res.end(), INF);
	priority_queue<EDGE> pq;
	res[s] = 0;
	pq.push({ s, 0 });
	while (pq.size()) {
		auto curTo = pq.top().to;
		auto curW = pq.top().w;
		pq.pop();
		if (chk[curTo])
			continue;
		chk[curTo]++;
		for (auto el : v[curTo]) {
			if (res[el.to] > curW + el.w) {
				res[el.to] = curW + el.w;
				pq.push({ el.to, curW + el.w });
			}
		}
	}
	memset(chk, 0, sizeof(chk));

	return;
}

// 다익스트라를 3번 적용해서 해결
int main() {
	scanf_s("%d %d", &n, &e);
	res.resize(n + 1);
	for (int i = 0; i < e; i++) {
		int num, to, w;
		scanf_s("%d %d %d", &num, &to, &w);
		v[num].push_back({ to, w });
		v[to].push_back({ num, w });
	}

	int key1, key2;
	scanf_s("%d %d", &key1, &key2);

	func(key1);
	int key1ToKey2 = res[key2];
	int key1ToEnd = res[n];

	func(1);
	int key1Dis = res[key1];
	int key2Dis = res[key2];

	func(key2);
	int key2ToEnd = res[n];

	int answer = 0;

	// overflow 조심
	if (key1Dis >= INF || key2Dis >= INF || key1ToEnd >= INF || key2ToEnd >= INF || key1ToKey2 >= INF) {
		printf("-1");
		return 0;
	}
	if (key2ToEnd + key1Dis > key1ToEnd + key2Dis) {
		if (key1ToEnd + key2Dis + key1ToKey2 >= INF) {
			printf("-1");
			return 0;
		}
		answer = key1ToEnd + key2Dis + key1ToKey2;
	}
	else {
		if (key2ToEnd + key1Dis + key1ToKey2 >= INF) {
			printf("-1");
			return 0;
		}
		answer = key2ToEnd + key1Dis + key1ToKey2;
	}

	printf("%d", answer);

	return 0;
}