백준 1504 특정한 최단 경로

 

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

 

서론

우선순위 큐를 이용한 다익스트라 알고리즘으로 풀이했다.

 

아이디어

다익스트라 알고리즘은

1 -> 2 -> 3-> 4가 최단경로일때

1에서 4까지의 최단경로는 1~2까지의 최단경로를 포함하고 2~3까지의 최단경로를 포함한다.

즉 목적지까지의 최단경로는 중간지점들의 최단경로 합이다.

 

두개의 정점이 n1, n2일때

시작정점부터 두개의 정점을 거쳐서 종료정점까지 가는 방법은

1. 시작정점 -> n1 -> n2 -> 종료정점

2. 시작정점 -> n2 -> n1 -> 종료정점 

두개의 방법이 있다.

 

1번 방법은

시작정점 -> n1의 최단경로, n1 -> n2의 최단경로, n2 -> 종료정점의 최단경로의 합을 구하면 되고

2번 방법도 마찬가지로

시작정점 -> n1의 최단경로, n1 -> n2의 최단경로, n2 -> 종료정점의 최단경로의 합을 구하면 된다.

즉 다익스트라를 1번방법에서 3번, 2번 방법에서 3번 실행시키고

1번과 2번의 최소값을 출력하면 된다.

단, 각 최단경로에서 값이 갱신되지 않아 INF가 나오면 방문할 수 없는 경로라서 -1을 출력해야한다.

 

위 방법은 다익스트라를 총 6번 실행시키는데

다익스트라를 3번만 실행해도 원하는 답을 얻을 수 있다.

 

다익스트라는 시작지점을 정해주면 모든 정점으로의 최단경로를 구할 수 있으므로

시작지점에서 다익스트라를 실행하면 시작~n1, 시작~n2의 최단경로를 얻을 수 있고

n1에서 실행하면 n1~n2, n1~종료를 얻을 수 있고

n2에서 실행하면 n2~n1, n2~종료를 얻을 수 있다.

 

구현

 

// c++

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

using namespace std;

int N, E, n1, n2;
int node[801];

// 1행 : 시작~n1, n1~n2, n2~끝, 행합계
// 2행 : 시작~n2, n2~n1, n1~끝, 행합계
int result[2][4]; 
vector<pair<int, int>>g[801];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;

void input() {
	cin >> N >> E;
	for (int i = 0; i < E; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		g[a].push_back({ c, b });
		g[b].push_back({ c, a });
	}
	cin >> n1 >> n2;
}

void shortestPath(int startNode) {
	memset(node, 0x7f, sizeof(node));
	node[startNode] = 0;
	pq.push({ 0, startNode });
	while (!pq.empty()) {
		int first = pq.top().first;
		int second = pq.top().second;
		int gSize = g[second].size();
		pq.pop();
		for (int i = 0; i < gSize; i++) {
			int nextFirst = g[second][i].first;
			int nextSecond = g[second][i].second;
			if (first + nextFirst <= node[nextSecond]) {
				node[nextSecond] = first + nextFirst;
				pq.push({ first + nextFirst, nextSecond });
			}
		}
	}
}

int main() {
	input();
	shortestPath(1);
	result[0][0] = node[n1];
	result[1][0] = node[n2];
	shortestPath(n1);
	result[0][1] = node[n2];
	result[1][2] = node[N];
	shortestPath(n2);
	result[0][2] = node[N];
	result[1][1] = node[n1];
	bool breakFlag = false;
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 3; j++) {
			if (result[i][j] == 0x7f7f7f7f) {
				breakFlag = true;
				break;
			}
			else {
				result[i][3] += result[i][j];
			}
		}
		if (breakFlag == true) break;
	} 
	if (breakFlag == true) cout << "-1";
	else cout << min(result[0][3], result[1][3]);
}