백준 1504 특정한 최단 경로

꼭 거쳐야 하는 노드가 각각

mustVertex1, mustVertex2

라고 하자.

그렇다면

노드1 -> mustVertex1 -> mustVertex2 -> 노드N

노드1 -> mustVertex2 -> mustVertex1 -> 노드N

의 경로 중 짧은 것이 정답이 된다.

각 경로는 다음과 같이 다익스트라 알고리즘을 세번 수행하면 결과를 얻을 수 있다.

1. 노드1에서 시작하는 다익스트라

이것으로 1 ->mustVertex1, 1 -> mustVertex2을 얻을 수 있다.

2. 노드N에서 시작하는 다익스트라

N -> mustVertex1, N -> mustVertex2 를 얻을 수 있다.

3. mustVertex1에서 시작하는 다익스트라

mustVertex1 -> mustVertex2를 얻을 수 있다.

한편, 그래프는 양방향이기 때문에 A->B의 거리가 B->A 거리와 같다.

그리고 각 경로중 하나라도 INT_MAX_에 해당하는 값이 있다면 경로가 없는것이므로 그 경로는 INT_MAX가 되고

두 경로 모두 INT_MAX일 경우 경로가 없으므로 -1을 출력하면 된다.

백준 1753 최단경로 http://deque.tistory.com/67 에서 쓰인 다익스트라 알고리즘을 쓰니 참고.

//deque.tistory.com

#define _CRT_SECURE_NO_WARNINGS
#define INT_MAX_ 2000000000
#define MIN_NUM(a, b) ((a)>(b) ? (b) : (a))

#include <iostream> 
#include <vector> 
#include <queue> 
#include <map>
#include <fstream> 
#include <string> 
#include <algorithm>
#include <functional>

using namespace std;
int N, E;
int mustVertex_1, mustVertex_2;
int OneToV1, OneToV2, V1ToN, V2ToN, V1ToV2;
vector<pair<int, int>> adj[20002];
int dist[20002];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

void dijkstra(int startNode) {

	for (int i = 1; i <= N; i++) {
		dist[i] = INT_MAX_;
	}
	dist[startNode] = 0;

	pq.push(make_pair(0, startNode));
	while (!pq.empty()) {
		int cost = pq.top().first;
		int now = pq.top().second;
		pq.pop();
		if (dist[now] < cost) continue;
		for (pair<int, int> next : adj[now]) {
			if (dist[next.second] > next.first + cost) {
				pq.push(make_pair(next.first + cost, next.second));
				dist[next.second] = next.first + cost;
			}
		}
	}

	return;
}

int main() {
	scanf("%d %d", &N, &E);

	int from, to, weight;
	for (int i = 0; i < E; i++) {
		scanf("%d %d %d", &from, &to, &weight);
		adj[from].push_back(pair<int, int>(weight, to));
		adj[to].push_back(pair<int, int>(weight, from));
	}
	scanf("%d %d", &mustVertex_1, &mustVertex_2);

	dijkstra(1);

	OneToV1 = dist[mustVertex_1];
	OneToV2 = dist[mustVertex_2];
	if (OneToV1 >= INT_MAX_ && OneToV2 >= INT_MAX_) {
		cout << -1 << endl;
		return 0;
	}

	dijkstra(N);

	V1ToN = dist[mustVertex_1];
	V2ToN = dist[mustVertex_2];

	if (V1ToN >= INT_MAX_ && V2ToN >= INT_MAX_) {
		cout << -1 << endl;
		return 0;
	}

	dijkstra(mustVertex_1);

	V1ToV2 = dist[mustVertex_2];

	if (V1ToV2 >= INT_MAX_) {
		cout << -1 << endl;
		return 0;
	}
	
	int root1 = -1;
	int root2 = -1;
	if (!(OneToV1 >= INT_MAX_ || V1ToV2 >= INT_MAX_ || V2ToN >= INT_MAX_)) {
		root1 = OneToV1 + V1ToV2 + V2ToN;
	}
	if (!(OneToV2 >= INT_MAX_ || V1ToV2 >= INT_MAX_ || V1ToN >= INT_MAX_)) {
		root2 = OneToV2 + V1ToV2 + V1ToN;
	}

	if (root1 == -1 && root2 == -1) {
		cout << -1 << endl;
	}
	else {
		cout << MIN_NUM(root1, root2) << endl;
	}


	return 0;
}