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

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

1504번: 특정한 최단 경로

방향성 없는 그래프가 주어진다. 1번 노드에서 N번 노드까지의 경로 중 v1과 v2를 경유하는 최단경로의 길이를 출력하는 문제다. 나는 단순하게 다익스트라를 세 번 써서 시도했지만 WA를 받았다. 코드를 다시 살펴보며 문제를 찾으려고 시도했지만, 내가 의도한대로 동작하기에 문제가 없었다. 결국 인터넷에서 답안을 찾아 보았는데, 1 - v1 - v2 - N의 경로 말고도 1 - v2 - v1 - N의 경로도 고려해야 함을 알지 못했다. 이렇게 수정한 뒤 코드를 제출하여 AC를 받았다.

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"
#define VI vector<int>
#define VVI vector<VI>
#define VVVI vector<VVI>
#define VP vector<pair<int, int>>
#define VVP vector<VP>

/* declare variables here */
int N, E;
VVP adj_list;

/* define debug functions here */


/* define functions here */
const int get_length(int from, int to) {
	// initialize the distance from s to every node
	VI dist(N, INF);
	dist[from] = 0;
	// traversal
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push(make_pair(from, 0));
	while (!pq.empty()) {
		// take out a top element of the priority queue
		auto [here, start_to_here] = pq.top();
		pq.pop();
		// if the distance is longer than stored distance, continue
		if (dist[here] < start_to_here) continue;
		// check the distance of edges from current node
		for (const auto& edge : adj_list[here]) {
			const auto& [neighbor, here_to_neighbor] = edge;
			// store the shorter path among whether go thru via current or not.
			if (start_to_here + here_to_neighbor < dist[neighbor]) {
				dist[neighbor] = start_to_here + here_to_neighbor;
				pq.push(make_pair(neighbor, dist[neighbor]));
			}
		}
	}
	return dist[to];
}

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	/* Write input codes here */
	cin >> N >> E;
	adj_list = VVP(N);
	FOR(i, E) {
		int a, b, c;
		cin >> a >> b >> c;
		adj_list[a - 1].push_back(make_pair(b - 1, c));
		adj_list[b - 1].push_back(make_pair(a - 1, c));
	}
	int v1, v2;
	cin >> v1 >> v2;

	/* Write solution codes here */
	long long v1v2 = -1;
	long long d1 = get_length(0, v1 - 1);
	long long d2 = get_length(v1 - 1, v2 - 1);
	long long d3 = get_length(v2 - 1, N - 1);
	if (d1 < INF && d2 < INF && d3 < INF)
		v1v2 = d1 + d2 + d3;
	long long v2v1 = -1;
	d1 = get_length(0, v2 - 1);
	d2 = get_length(v2 - 1, v1 - 1);
	d3 = get_length(v1 - 1, N - 1);
	if (d1 < INF && d2 < INF && d3 < INF)
		v2v1 = d1 + d2 + d3;
	if (v1v2 == -1)
		cout << v2v1 << EL;
	else if (v2v1 == -1)
		cout << v1v2 << EL;
	else
		cout << (v1v2 < v2v1 ? v1v2 : v2v1) << EL;

	return 0;
}