백준 1504 : 특정한 최단 경로

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

1504번: 특정한 최단 경로

 

최단경로 문제인데 다른 점은 문제에서 주어지는 v1, v2 노드를 꼭 거쳐서 1번 노드부터 N번 노드까지 가야한다는 것이다. 간선이 모두 양방향이므로 다음과 같이 풀 수 있다.

 

 v1을 기준으로 다익스트라를 돌려서 v1에서 1로 가는 최단 경로, v1에서 N으로 가는 최단 경로 값을 얻고, 마찬가지로

v2를 기준으로 다익스트라를 돌려서 v1에서 1로 가는 최단 경로, v2에서 N으로 가는 최단 경로, v2에서 v1로 가는 최단 경로 값을 얻는다. 모두 양방향 간선이므로 v2로 얻은 v2에서 v1으로 가는 경로의 길이나, v1으로 얻은 v1에서 v2로 가는 경로의 길이는 같다

 

이후 구해진 값들을 더해서

1 -> v1 -> v2 -> N 으로 가는 경로의 길이와 1 -> v2 -> v1 -> N 으로 가는 경로의 길이를 비교해주면 된다.

 

코드로 구현하면 아래와 같다.

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

#define DIST first
#define POS second
using namespace std;
using pii = pair<int, int>;

int n, v1, v2;
vector<pii> edge[801];
int dist[801];

void dijkstra(int start) {
	int cur, cur_dist, npos, n_dist;
	priority_queue<pii> pq;
	pq.emplace(0, start);
	dist[start] = 0;

	while (!pq.empty()) {
		cur = pq.top().POS;
		cur_dist = -pq.top().DIST;
		pq.pop();

		if (dist[cur] < cur_dist) continue;
		for (int i = 0; i < edge[cur].size(); i++) {
			npos = edge[cur][i].POS;
			n_dist = cur_dist + edge[cur][i].DIST;

			if (dist[npos] > n_dist) {
				dist[npos] = n_dist;
				pq.emplace(-n_dist, npos);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int e, v1, v2, _dist;
	int oneToV1, v1ToN, oneToV2, v2ToN, v1v2, v2v1;
	cin >> n >> e;
	while (e--) {
		cin >> v1 >> v2 >> _dist;
		edge[v1].emplace_back(_dist, v2);
		edge[v2].emplace_back(_dist, v1);
	}
	cin >> v1 >> v2;

	for (int i = 1; i <= n; i++) 
		dist[i] = 1e7;
	dijkstra(v1);
    //1 -> v1 최단 경로
	oneToV1 = dist[1];
    //v1 -> N 최단 경로
	v1ToN = dist[n];

	for (int i = 1; i <= n; i++)
		dist[i] = 1e7;
	dijkstra(v2);
    //1 -> v2 최단 경로
	oneToV2 = dist[1];
    //v2 -> N 최단 경로
	v2ToN = dist[n];

	//1 -> v1 -> v2 -> N 최단 경로
	v1v2 = oneToV1 + dist[v1] + v2ToN;
    //1 -> v2 -> v1 -> N 최단 경로
	v2v1 = oneToV2 + dist[v1] + v1ToN;

	//둘 다 도달하지 못하는 경우
	if (v1v2 >= 1e7 && v2v1 >= 1e7) cout << -1;
    //그렇지 않은 경우 더 작은 경로 출력
	else cout << (v1v2 < v2v1 ? v1v2 : v2v1);
	return 0;
}

메모리: 5744 kb

시간: 56 ms

 

추가로 주의해야할 점은, 보통 dist배열의 값을 1e9와 같은 값으로 초기화할텐데 이 문제의 경우 최악의 경우에 v1v2나 v2v1이 3e9가 될 수 있기 때문에 오버플로우가 발생할 수 있다.