[C/C++] 백준 1504번 - 특정한 최단 경로 (다익스트라)

 

 

<코드>

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

#define INF 2100000000 // 21억

int a, b, c, v1, v2;
int N, E;
long long x, y;
long long result_1[801], result_v1[801], result_v2[801];
vector<pair<int, int>> v[801];

void dijkstra(int start, long long* result)
{
	queue<int> q;
	for (int i = 1; i <= N; i++)
		result[i] = INF;
	
	result[start] = 0;
	q.push(start);

	while (!q.empty())
	{
		int node = q.front();
		int dist = result[node];
		q.pop();

		for (int i = 0; i < v[node].size(); i++)
		{
			int next_node = v[node][i].first;
			int next_dist = v[node][i].second;

			if (result[next_node] > dist + next_dist)
			{
				result[next_node] = dist + next_dist;
				q.push(next_node);
			}
		}
	}
}

int main()
{
	cin >> N >> E;

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

	cin >> v1 >> v2;

	dijkstra(1, result_1);
	dijkstra(v1, result_v1);
	dijkstra(v2, result_v2);

	x = result_1[v1] + result_v1[v2] + result_v2[N];
	y = result_1[v2] + result_v2[v1] + result_v1[N];
	
	//cout << result_1[v1] << " " << result_v1[v2] << " " << result_v2[N] << endl;
	//cout << result_1[v2] << " " << result_v2[v1] << " " << result_v1[N] << endl;
	
	if (min(x, y) >= INF) cout << -1;
	else cout << min(x, y);
}

 

풀이 방법

 

result_1[x] : 1번 정점에서 x 정점까지의 최단거리

result_v1[x] : v1 정점에서 x 정점까지의 최단거리

result_v2[x] : v2 정점에서 x 정점까지의 최단거리

 

다익스트라를 이용하게 되면 특정 노드에서 각 노드까지의 최단거리를 구할 수 있다. 

1번 정점 ~ v1 정점 ~ v2 정점 ~ N번 정점까지의 경로(파란색)와
1번 정점 ~ v2 정점 ~ v1 정점 ~ N번 정점까지의 경로(빨간색)를

비교해서 최단거리를 구하는 알고리즘으로 문제를 풀이하였다.

 

예제 입력 1로 코드를 실행시킬 때 아래의 코드를 추가해서 result 배열들의 값들을 확인해보면

cout << result_1[v1] << " " << result_v1[v2] << " " << result_v2[N] << endl;
cout << result_1[v2] << " " << result_v2[v1] << " " << result_v1[N] << endl;

 

경로	거리
1~v1	3
v1~v2	3
v2~N	1
합계	7

경로	거리
1~v2	5
v2~v1	3
v1~N	4
합계	12

따라서 예제 입력 1의 최단거리는 7이 정답이 된다.

그리고 조건을 확인했을 때 거리의 최댓값은 1000이므로 합계를 구할 때 int형을 사용하여도 오버플로우가 발생하지 않을 것 같지만 만약 합계에 INF값이 들어오게 되고 그 INF값이 지나치게 클 경우 오버플로우가 일어날 가능성이 있기 때문에 long long형으로 구해줘야 합니다. 

 

www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로