[BOJ 1504] 특정한 최단 경로

 

1504번: 특정한 최단 경로

[문제 조건]

1. 방향성이 없는 그래프 : 무향 그래프

2. 정점의 개수 (1 <= N <= 800), 간선의 개수 (1 <= E <= 200000)

3. 두 개의 정점 X, Y를 반드시 거쳐가야 함 : X와 Y는 1일 수 없으며, N일 수도 없다.

4. 한 번 방문한 정점과 간선을 재방문할 수 있다.

 

 

이 때, 1 -> N번까지 X,Y를 거쳐서 갈 수 있는 최단 경로를 구하는 문제입니다.

문제의 조건에 따라, 있다면 최단 경로의 최소비용을 출력해주면 되고 없으면 -1을 출력합니다.

 

1 -> N까지 거쳐갈려면, 반드시 1 -> X를 갈 수 있어야 하고 1 -> Y도 갈수 있어야 하며 1 -> N도 갈수 있어야 합니다.

  * 셋 중 하나라도 만족하지 못한다면 경로가 없다는 뜻입니다.

 

즉, 

1) 1 -> X -> Y -> N : Dijkstra(1,X) + Dijkstra(X, Y) + Dijkstra(Y,N)

2) 1 -> Y -> X -> N : Dijkstra(1,Y) + Dijkstra(Y, X) + Dijkstra(X,N)

두 가지 경우에 답이 있습니다. 

 

우선순위 큐를 이용한 다익스트라를 이용하여 문제를 풀이하겠습니다.

1) 최소 비용 누적을 위한 Dist배열 필요

   N은 최대 800이니, Dist[810] 정도로 선언하고  

   이 배열의 각 원소 값은 INF = 충분히 큰 값으로 선언하여 Dist배열의 값을 변경해나가줍니다.

 

2) 무향그래프 : vector<pair<int,int>> graph[810] 으로 양 정점의 간선 정보를 모두 저장해줄 graph

 

3) prority_queue<pair<int,int>> pq : 우선순위 큐를 이용하여 수행, first에는 시작 정점의 번호, second에는 비용 저장

 

각 Dijkstra를 수행할 때마다 Dist배열을 INF로 계속 초기화해주어야 합니다. 즉, 총 6번의 초기화가 됩니다.

이유는, 위에서 설명했던 [문제조건]의 4. 한 번 방문한 정점과 간선을 재방문할 수 있다라는 조건때문에

INF로 계속 초기화하며 재방문할 수 있는 여지를 만들어주어야 하기 때문입니다.

만약에 초기화하지 않는다면, 다익스트라의 알고리즘에 의해 다음 다익스트라를 수행할 때에도 최소비용이 저장되있는 것을 이용하는 상황이 오게 됩니다. 이는 재방문을 허용하지 않습니다.

 

 

1) 1 -> X -> Y -> N : Dijkstra(1,X) + Dijkstra(X, Y) + Dijkstra(Y,N)

2) 1 -> Y -> X -> N : Dijkstra(1,Y) + Dijkstra(Y, X) + Dijkstra(X,N)

이 둘을 비교해서 나온 최소값이 INF보다 작다면 답 출력, 아니라면 -1

 

 

 

/*

1부터 출발해서 정점 X와 Y를 모두 거쳐서 N에 도착하는 최단 경로

1) 1->X->Y->N

2) 1->Y->X->N

1 -> X + X -> Y + Y -> N

1 -> Y + Y -> X + X -> N

*/

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

#define INF 1e9
using namespace std;

vector<pair<long long, long long>> graph[810];

long long dist[810];

long long dijkstra(int start, int end)
{
	priority_queue<pair<long long,long long>> pq;
	fill(dist, dist + 809, INF);
	dist[start] = 0;
	pq.push({ start,0 });

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

		if (dist[cur] < cost) continue;

		for (int i = 0; i < graph[cur].size(); i++)
		{
			int next = graph[cur][i].first;
			int next_cost = cost + graph[cur][i].second;

			if (dist[next] > next_cost)
			{
				dist[next] = next_cost;
				pq.push({ next,-next_cost });
			}
		}
	}
	return dist[end];
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	int V, E;

	cin >> V >> E;

	int a, b, c;
	for (int i = 0; i < E; i++)
	{
		cin >> a >> b >> c;

		graph[a].push_back({ b,c });
		graph[b].push_back({ a,c });
	}
	int X, Y;
	cin >> X >> Y;

	long long ans1 = dijkstra(1, X) + dijkstra(X, Y) + dijkstra(Y, V);
	long long ans2 = dijkstra(1, Y) + dijkstra(Y, X) + dijkstra(X, V);

	long long res = min(ans1, ans2);
	if (res < INF) cout << res;
	else cout << "-1";
}