[1504] 특정한 최단 경로

문제

특정한 조건 하에 1번 정점에서 N번 정점까지의 최단 거리를 구하는 문제이다. 이 문제에서 주어진 특정한 조건은 임의로 주어진 점 v1,v2를 반드시 통과한다는 것이다.

해결

정점의 최단 거리를 구하는 알고리즘은
1. 다익스트라 알고리즘
2. 벨만포드 알고리즘
3. 플로이드-와샬 알고리즘이 있다.

이 중에서 우선순위 큐를 이용하여 가장 빠르게 구할 수 있는 다익스트라 알고리즘을 사용해서 구할 것이다.

임의로 주어진 점 v1,v2를 반드시 통과하는 최단거리를 구하기 위해서는

1 -> v1 -> v2 -> N
1 -> v2 -> v1 -> N

두 가지 경우 중 하나일 것이다.

내가 푼 방식은
v1->v2 와 v2->v1의 거리는 같기 때문에
총 5번의 다익스트라 알고리즘을 통하여 답을 도출했다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const long INF = 10000000000;
int N, E;
int v1, v2;

vector<pair<long long, long long>> vec[801];

long long dijkstra(int start, int end)
{
	long long dis[801];
	for (int i = 1; i <= N; i++) dis[i] = INF;
	priority_queue<pair<long long, long long>> pq;

	pq.push(make_pair(0, start));
	dis[start] = 0;

	while (!pq.empty()) {
		long long curTime = -pq.top().first;
		int cur = pq.top().second;
		pq.pop();

		for (int i = 0; i < vec[cur].size(); i++) {
			long long nextTime = vec[cur][i].second;
			int next = vec[cur][i].first;

			if (dis[next] > nextTime + curTime) {
				dis[next] = nextTime + curTime;
				pq.push(make_pair(-dis[next], next));
			}
		}
	}

	return dis[end];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> E;

	for (int i = 0; i < E; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		vec[a].push_back(make_pair(b, c));
		vec[b].push_back(make_pair(a, c));
	}

	cin >> v1 >> v2;

	long long common = dijkstra(v1, v2);
	long long route1 = dijkstra(1, v1) + dijkstra(v2, N);
	
	long long route2 = dijkstra(1, v2) + dijkstra(v1, N);

	long long answer = min(route1, route2);
	if (answer == INF || answer + common == INF) cout << "-1" << '\n';
	else cout << answer+common << '\n';
}

피드백

1. 답을 도출하는 과정에서 몇 번의 오류가 있었다.

   • 자료형을 제대로 판별하지 않았다. (최대 long long 값이 나올 수 있는 것을 간과했다)
   • v1는 1이고 v2는 N인 경우를 간과했다.

2. 최적화

   • 다익스트라 알고리즘에 대해 다시 생각해보자

   • 다익스트라 알고리즘을 통해 알 수 있는 것
     => 시작점에서의 각 정점까지의 최단거리

   • 총 5번의 다익스트라 알고리즘이 필요했을까?

   • 1->v1,v2 / v1-> v2,N / v2 -> N 으로 총 3번의 다익스트라 알고리즘을 통해 구할 수 도 있었을 것이다.