[baekjoon 1504] 특정한 최단 경로 (다익스트라) (C++)

www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

1번부터 N번까지 갈 수 있는 최단 경로 중 주어진 두 점을 지나는 최단 경로를 출력한다.

 

가중치 있는 그래프이므로 다익스트라를 이용하고, 나올 수 있는 최단경로의 경우는

1. 시작점 1 -> 주어진 점 a -> 주어진 점 b -> 끝점 n

2. 시작점 1 -> 주어진 점 b -> 주어진 점 a -> 끝점 n

이다.

 

즉, 다익스트라를 3번 이용해서 각각의 경우에 해당하는 최단 경로를 계산해서 더해주면 된다.

또는, 경로가 없다면 -1을 출력한다.

 

다익스트라(1 -> a) + 다익스트라(a -> b) + 다익스트라(b -> n)와

다익스트라(1 -> b) + 다익스트라(b -> a) + 다익스트라(a -> n) 중 최솟값이다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

#define INF 987654321

using namespace std;

int n, e, dist[801][3], from, to, dis, mustfrom, mustto;
vector<pair<int, int>> v[801];
priority_queue < pair<int, int>, vector<pair<int, int>>, greater< pair<int, int>>> pq;

void BFS(int start, int idx) {
	pq.push(make_pair(start, 0));
	dist[start][idx] = 0;

	while (!pq.empty()) {
		int now = pq.top().first;
		int now_dist = pq.top().second;
		pq.pop();

		for (int i = 0; i < v[now].size(); i++) {
			int next = v[now][i].first;
			int next_dist = v[now][i].second;

			if (dist[next][idx] > dist[now][idx] + next_dist) {
				dist[next][idx] = dist[now][idx] + next_dist;
				pq.push(make_pair(next, dist[next][idx]));
			}
		}
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> e;
	for (int i = 0; i < e; i++) {
		cin >> from >> to >> dis;
		v[from].push_back(make_pair(to, dis));
		v[to].push_back(make_pair(from, dis));
	}
	cin >> mustfrom >> mustto;

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 3; j++) {
			dist[i][j] = INF;
		}
	}

	BFS(1, 0);

	BFS(mustfrom, 1);

	BFS(mustto, 2);

	int ans1 = 0;
	int ans2 = 0;

	if (dist[mustfrom][0] == INF || dist[mustto][1] == INF || dist[n][2] == INF)
		ans1 = -1;
	else
		ans1 = dist[mustfrom][0] + dist[mustto][1] + dist[n][2]; // 1 -> 2 -> 3-> 4

	if (dist[mustfrom][1] == INF || dist[mustto][0] == INF || dist[n][2] == INF)
		ans2 = -1;
	else
		ans2 = dist[mustto][0] + dist[mustfrom][2] + dist[n][1]; //1->3->2->4

	if (ans1 != -1 && ans2 != -1)
		cout << min(ans1, ans2);
	else if (ans1 == -1 && ans2 != -1)
		cout << ans2;
	else if (ans1 != -1 && ans2 == -1)
		cout << ans1;
	else
		cout << -1;
}

다익스트라를 3번 해야 하기 때문에 최단 거리를 저장하는 배열을 dist [801][3]으로 선언했다.