[c++] 백준 - 특정한 최단 경로

1. 문제

2. 입출력 및 예제

3. 문제 해설

처음 이 문제를 읽었을 때 잘못 이해해서 얼마나 고생을 했던지... 나는 v1, v2를 이어주는 간선을 무조건 지나야한다는 줄 알고 처음에는 1 ~ v1, v2의 다익스트라를 1번 수행하고 N ~ v1,v2를 수행해서 1 ~ v1 + v1 ~ v2 + v2 ~ N과 1 ~ v2 + v2 ~ v1 + v1 ~ N 값 중 더 작은 값을 구하려고 했다. .. 다익스트라 2번이면 되었기 때문이다. 

 

하지만 계속 틀렸다...!

그래서 왜일까 문제를 다시 읽어보니 v1, v2를 이어주는 간선을 무조건 지나가야 하는 것이 아니라 v1, v2를 그냥 지나가기만 하면 되었다. ... 

 

그래서 생각 방향을 바꾸어 다시 생각을 해보니 이 문제가 오히려 갔던 길을 다시 가도 된다고 하는 조건은 오히려 쉬운 조건이었다. 단순히 다익스트라 3번을 수행하면 될 거 같았다. 

 

1. 1 을 시작점으로 다익스트라 알고리즘을 수행한다. 그러면 V1, V2로 갈 수 있는 최단 거리가 나올 것이다. 
2. V1을 시작점으로 다익스트라 알고리즘을 수행한다. 그러면 V2, N로 갈 수 있는 최단 거리가 나올 것이다. 
3. N을 시작점으로 다익스트라 알고리즘을 수행한다. 그러면 V1, V2로 갈 수 있는 최단 거리가 나올 것이다. 

우리가 갈 수 있는 루트는 다음과 같다. 

• A. 1 -> V1 -> V2 -> N
• B. 1 -> V2 -> V1 -> N

A번의 경우 1번 다익스트라에서 1-> V1 값과 2번 다익스트라에서 V1->V2값 3번 다익스트라에서 V2 -> N 값을 더해준 것

B번의 경우 1번 다익스트라에서 1->V2 값과 2번 다익스트라에서 V2->V1(위와 같다.) 3번 다익스트라에서 V1->N값을 더해준 것 중 작은 것을 선택하면 된다. 중간에 overflow는 주의해야한다. 중간에 저장하는 값들을 int로 설정할 시 

초기값을 INF값으로 설정하는 다익스트라 알고리즘의 특성 상 overflow가 발생할 수 있다. 

 

4. 코드

#pragma warning (disable : 4996)
#define INF 0x3f3f3f3f
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
struct n_t {
	int node;
	int cost;
	inline bool operator < (const n_t &ref) const {
		return this->cost > ref.cost;
	}
}; // 구조체 정의 
int N, E; // 정점의 개수와 간선의 개수
vector<n_t> AL[801]; // 인접 리스트
int dist[801]; // 거리배열
priority_queue<n_t> q1;
priority_queue<n_t> q2;
int u, v;
ll ans;
int midCost;
ll midU, midV , mid2U,mid2V; // 1번의 다익스트라가 끝난 후 반드시 지나야하는 두 정점 중 작은 값
void input() {
	scanf("%d %d", &N, &E);
	for (int i = 0; i < E; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		AL[a].push_back({ b,c });
		AL[b].push_back({ a,c }); // 방향성이 없다. 
	}
	scanf("%d %d", &u, &v); // 반드시 지나야하는 u v
}
void sol() {
	for (int i = 0; i < 801; i++) {
		dist[i] = INF;
	} // 무한대로 초기화
	dist[1] = 0;
	q1.push({ 1, 0 });
	while (q1.size()) {
		auto curr = q1.top(); q1.pop();
		for (auto next : AL[curr.node]) {
			int cost = dist[curr.node] + next.cost;
			if (dist[next.node] > cost) {
				dist[next.node] = cost;
				q1.push({ next.node, cost });
			}
		}
	} // 다익스트라 1번 
	// u,v 둘 다 무한대라면 불가능하다. u]
	midU = dist[u];
	midV = dist[v];
	for (int i = 0; i < 801; i++) {
		dist[i] = INF;
	} // 무한대로 초기화
	dist[u] = 0;
	q2.push({ u, 0 });
	while (q2.size()) {
		auto curr = q2.top(); q2.pop();
		for (auto next : AL[curr.node]) {
			int cost = dist[curr.node] + next.cost;
			if (dist[next.node] > cost) {
				dist[next.node] = cost;
				q2.push({ next.node, cost });
			}
		}
	} // 다익스트라 2번 u -> v , v->u;
	mid2V = dist[v];
	mid2U = dist[v];
	for (int i = 0; i < 801; i++) {
		dist[i] = INF;
	} // 무한대로 초기화
	dist[N] = 0;
	q2.push({ N, 0 });
	while (q2.size()) {
		auto curr = q2.top(); q2.pop();
		for (auto next : AL[curr.node]) {
			int cost = dist[curr.node] + next.cost;
			if (dist[next.node] > cost) {
				dist[next.node] = cost;
				q2.push({ next.node, cost });
			}
		}
	} // 다익스트라 3번 N->u,v
	ll tmp1 = midU + mid2V + dist[v];
	ll tmp2 = midV + mid2U + dist[u];
	ans = min(tmp1, tmp2);
	if (ans >= INF) {
		puts("-1\n");
	}
	else {
		printf("%lld", ans);
	}
	
}
int main() {
	input();
	sol();
	return 0;
}