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

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

1504번: 특정한 최단 경로

풀이

다익스트라 문제가 점점 익숙해지고 있다. 우선 문제를 살펴보자면,

'특정 정점을 무조건 들려야한다' 라는 전제조건이 있다.

 

만약 정점을 2곳을 꼭 들려야 한다면 출발지점에서 해당 정점 2곳을 들리는 다익스트라 함수,

해당 정점으로부터 도착지점까지 가는 다익스트라 함수 즉 3번 탐색을 하면된다.

 

1. 시작점에서 입력받은 정점까지 가는 최단거리

2. 반드시 거쳐야하는 두 정점중 하나인 v1에서부터 입력받은 정점까지 가는 최단거리

3. 반드시 거쳐야하는 두 정점중 하나인 v2에서부터 입력받은 정점까지 가는 최단거리

 

이렇게 쪼개어 생각하면 쉽다.

 

그림으로 표현하면 아래와 같다.

1 ~ 2 ~ 3 ~ 4로 가는방법과

1 ~ 3 ~ 2 ~ 4로 가는 방법이 있다.

 

전자에서는 3 -> 3 -> 1 이 될 것이고, 

후자에서는 5 -> 3 -> 5가 될것이다. 

 

Code ( C++ )

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

int N, E;
int a, b, c;
int v1, v2;

vector<pair<int, int>> _vec[801];
int result[801];
int node1[801], node2[801];
queue<int> q;

void Dijkstra(int idx, int* result)
{
	for (int i = 1; i <= N; i++)
		result[i] = INF;

	result[idx] = 0;
	q.push(idx);

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

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

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

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

	cin >> v1 >> v2;

	Dijkstra(1, result);
	Dijkstra(v1, node1);
	Dijkstra(v2, node2);

	X = result[v1] + node1[v2] + node2[N];
	Y = result[v2] + node2[v1] + node1[N];

	if (min(X, Y) >= INF) 
		cout << -1;
	else 
		cout << min(X, Y);
}