[C++] 1504. 특정한 최단 경로 (ft.Djikstra)

출처

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

 

 

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

 

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

 

풀이

다익스트라의 응용 문제.

v1과 v2를 무조건 지나야 하므로 다음과 같은 방법을 생각해 볼 수 있다. 

1 ) 1 → v1 → v2 → N

2 ) 1 → v2 → v1 → N 

 

(1)을 예시로 들자면, 특정 경로의 최단 거리는 (1 → v1) + (v1 → v2) + (v2→N) 이다. 그러므로, 각 3가지 경우의 다익스트라의 합이 특정 경로의 최단 거리가 된다. 그리고, 이 두가지 특정 경로를 비교하여 더 짧은 값을 비교하여 정답을 구한다.

 

여기서 여러가지 경우의 수를 생각해야 한다.

(1)번 경우 혹은 (2)번 경우의 경로가 없는 경우에는 둘 중 최단거리를 찾아야 하기 때문에 INT_MAX로 설정하여 비교한다.

(1)번 경우와 (2)번 경우 모두 경로가 없는 경우에는 둘 다 INT_MAX가 되기 때문에, -1로 변환하는 과정이 필요하다.

v1과 v2가 1이거나, N인 경우도 있기 때문에 자기 자신까지의 거리 또한 추가해줘야 한다. 그렇지 않는다면, 1 → 2 → 1 식으로 계산이 된다....

#include <bits/stdc++.h>
#define MAX 801
using namespace std;

int N, E;	// 정점의 개수, 간선의 개수
vector<pair<int, int>> node[MAX];
int v1, v2;	// 반드시 저쳐야 하는 정점 번호 
int a, b, c;
int result;

void input_data();
int djikstra(int start_point, int end_point);
int solution();

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	input_data();
	result = solution();
	cout << result << endl;
	return 0;
}

void input_data() {
	cin >> N >> E;
	for (int i = 0; i < E; ++i){
		cin >> a >> b >> c;
        // 양방향 연결
		node[a].push_back(make_pair(c, b));
		node[b].push_back(make_pair(c, a));
	}
    // 자기 자신 -> 자기 자신까지의 거리 추가
	for (int i = 1; i <= N; ++i)	{
		node[i].push_back(make_pair(0, i));
	}
	cin >> v1 >> v2;
}

int djikstra(int start_point, int end_point) {
	int distance[MAX];
	fill(distance, distance + MAX, INT_MAX);
	priority_queue<pair<int, int>> q;
	q.push({ 0, start_point });
	while (!q.empty()) {
		int cost = -q.top().first;
		int curr_point = q.top().second;
		q.pop();
		if (distance[curr_point] < cost) continue;
		for (int i = 0; i < node[curr_point].size(); ++i) {
			int curr_cost = cost + node[curr_point][i].first;
			if (curr_cost < distance[node[curr_point][i].second]) {
				distance[node[curr_point][i].second] = curr_cost;
				q.push({ -curr_cost, node[curr_point][i].second });
			}
		}
	}
	//cout << distance[end_point] << endl;
	return distance[end_point] == INT_MAX ? -1 : distance[end_point];
}

int solution() {
	int track1[4] = {1, v1, v2, N};
	int track2[4] = { 1, v2, v1, N };
	int result1 = 0, result2 = 0, djik_result;
	for (int i = 0; i < 3; ++i){
		djik_result = djikstra(track1[i], track1[i + 1]);
		if (djik_result == -1) {
			result1 = INT_MAX;
			break;
		}
		result1 += djik_result;
	}
	//cout << "result1 : " << result1 << endl;
	for (int i = 0; i < 3; ++i) {
		djik_result = djikstra(track2[i], track2[i + 1]);
		if (djik_result == -1) {
			result2 = INT_MAX;
			break;
		}
		result2 += djik_result;
		
	}
	//cout << "result2 : " << result2 << endl;
	if (result1 == result2 && result1 == INT_MAX){
		return -1;
	}
	return result1 < result2 ? result1 : result2;
}

나의 경우에는, 양방향 연결을 잊어서 3%에서 반례가 나왔고, 자기 자신까지의 거리와 두가지 모두 경로가 없을 때의 반례를 생각해주지 못해서 82%에서 반례가 나왔다.