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

순간 다익스트라 어떻게 작성했지? 하고 헷갈렸던 문제이다.

다익스트라 알고리즘은 우선순위 큐를 사용해야 하기 때문에 이 컨테이너를 사용할 때 greater<>을 사용하길 원한다면 weight, vertex 순으로 pair을 만들어서 넣어야한다.

이 문제는 다익스트라를 3번 수행함으로서 해결할 수 있다. 

1번에서 시작하는 경우, u에서 시작하는 경우, v에서 시작하는 경우에 대해서 다익스트라를 각각 돌리고,

1번에서는 u, v까지의 최소 거리, u에서는 v와 n까지의 거리, v에서는 n까지의 거리를 구한 후

1-u-v-n, 1-v-u-n의 Case에 대해서 min값을 구해주면 된다.

예상하지 못했던것은 Overflow의 존재이다. INF값을 먼저 체크하지 않고 min값을 구한 후 체크를 하기 때문에 Overflow조건, 혹은 u에서 v까지의 간선이 없는 경우를 체크해주면 된다. 

골드문제 답게 조금 생각해볼 것이 많았던 문제였다. 

 

#include <bits/stdc++.h>
#define endl '\n'
#define INF 987654321
#define pii pair<int, int>
using namespace std;

vector<pii> graph[801];
int dist[801];

int n, e;
int u, v; //반드시 지나가야하는 간선
int a, b, c;

void dijikstra (int start) {
	for (int i = 0; i <= n; i++) 
		dist[i] = INF;
	dist[start] = 0;
	priority_queue<pii, vector<pii>, greater<pair<int, int>>> pq;
	pq.push({ 0, start });
	while (!pq.empty()) {
		int current = pq.top().second;
		int currentDist = pq.top().first;
		pq.pop();
		for (int i = 0; i < graph[current].size(); i++) {
			int next = graph[current][i].first;
			int nextDist = graph[current][i].second;
			if (dist[next] > currentDist + nextDist) {
				dist[next] = currentDist + nextDist;
				pq.push({ dist[next],next });
			}
		}
	}
}

int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> e;
	for (int i = 0; i < e; i++) {
		cin >> a >> b >> c;
		graph[a].push_back({ b, c });
		graph[b].push_back({ a, c });
	}

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

	cin >> u >> v;
	
	dijikstra(1);
	int start_u = dist[u];
	int start_v = dist[v];

	dijikstra(u);
	int u_v = dist[v];
	int u_n = dist[n];

	dijikstra(v);
	int v_n = dist[n];

	int ans = INF;
	ans = min(ans, start_u + u_v + v_n);
	ans = min(ans, start_v + u_v + u_n);

	if (ans == INF || u_v == INF) cout << -1 << endl;
	else cout << ans << endl;

	return 0;
}