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

특정한 최단 경로
https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
int N, E;
set<pair<int, int>> arr[8001];
int ans[8001];
int solution(register int start, register int end) {
	for (register int i = 0; i <= N; ++i)
		ans[i] = static_cast<int>(1e8);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
	q.push(make_pair(0, start));
	ans[start] = 0;
	while (!q.empty()) {
		auto v = q.top(); q.pop();
		auto x = v.second, c1 = v.first;
		if (ans[x] < c1)
			continue;
		for (auto iter = arr[x].begin(); iter != arr[x].end(); ++iter) {
			auto y = iter->first, c2 = iter->second;
			if (ans[y] > c1 + c2)
				ans[y] = c1 + c2, q.push(make_pair(ans[y], y));
		}
	}
	return ans[end];
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> N >> E;
	for (register int e = 0, a, b, c; e < E; ++e)
		cin >> a >> b >> c, arr[a].insert(make_pair(b, c)), arr[b].insert(make_pair(a, c));
	register int a, b;
	cin >> a >> b;
	auto ans1 = solution(1, a) + solution(a, b) + solution(b, N);
	auto ans2 = solution(1, b) + solution(b, a) + solution(a, N);
	auto answer = min(ans1, ans2);
	if (answer >= static_cast<int>(1e8))
		cout << -1;
	else
		cout << answer;
	return 0;
}
// *&)*@*

1. 다익스트라 알고리즘을 통해서 풀 수 있는 문제입니다.
2. 문제에서 주어진 반드시 거쳐야 하는 v1, v2가 있습니다.
3. 따라서 1->v1, v1->v2, v2->N 또는 1->v2, v2->v1, v1->N 둘 중 최소값이 v1, v2를 반드시 거치는 최단 경로입니다.