백준 : 1504번 특정한 최단 경로 다익스트라(c++)

백준 링크

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

1504번: 특정한 최단 경로

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	73109	19048	12895	24.638%

문제

방향성이 없는 그래프가 주어진다. 세준이는 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을 출력한다.

예제 입력 1

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

예제 출력 1

7

코드 풀이

이번 문제는 다익스트라 문제로 어려운 축에 속했던 문제라 생각된다.

이번 문제는 일반적인 다익스트라와 다르게 이번 문제는 시작노드에서 끝노드까지 가는 도중 무조건적으로 두 위치를 지나가야 되는 문제입니다.

두 노드를 무조건적으로 지나야하기 때문에 아래와 같은 방법의 다익스트라를 총 3번을 돌려야 합니다.

• 시작노드 출발
  시작노드에서 MustA노드까지의 거리와 MustB노드까지의 거리를 구해야 함
• MustA노드 출발
  MustA노드에서  MustB노드까지의 거리와 N노드까지의 거리를 구해야 함
• MustB노드 출발
  MustB 노드에서 N노드까지의 거리를 구해야 함

위 5가지의 Cost를 구하는 이유는

Start - MustA - MustB - End

Start - MustB - MustA - End

두 가지의 방법이 가능하기 때문이다.

그래서 5개의 노드 Cost를 구하고  위 2가지의 방법의 총 합 가격 중 더 작은 값이 정답이 되게 되고 INTMAX보다 크거나 같다면 End까지 도달할 수 없다는 의미이므로 -1 출력하면 된다.

 

코드

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

using namespace std;

#define INTMAX 100000000
#define MAX_N 801

vector<pair<int, int>> Graph[MAX_N];
int Dist[MAX_N];

void Dijkstra(int StartNode)
{
	fill(Dist, Dist + MAX_N, INTMAX);
	// Node, Cost
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	// 시작지점, 시작지점 가격
	// 우선순위 큐는 앞의 Value를 활용해 정렬을 하기때문에 Cost를 first에 넣음
	pq.push({ 0, StartNode });
	Dist[StartNode] = 0;

	while (!pq.empty())
	{
		int CurCost = pq.top().first;
		int CurNode = pq.top().second;
		pq.pop();

		if (Dist[CurNode] < CurCost)
			continue;

		int Size = static_cast<int>(Graph[CurNode].size());
		for (int i = 0; i < Size; ++i)
		{
			int NextNode = Graph[CurNode][i].first;
			int NextCost = Graph[CurNode][i].second + CurCost;

			if (Dist[NextNode] > NextCost)
			{
				pq.push({ NextCost, NextNode });
				Dist[NextNode] = NextCost;
			}
		}
	}
}

int main()
{
	int N, E;

	cin >> N >> E;

	// 그래프 연결
	for (int i = 0; i < E; ++i)
	{
		int NodeA, NodeB, Cost;
		cin >> NodeA >> NodeB >> Cost;
		Graph[NodeA].push_back({ NodeB, Cost });
		Graph[NodeB].push_back({ NodeA, Cost });
	}

	// 무조건 가야하는 노드 두개
	int MustNodeA, MustNodeB;
	cin >> MustNodeA >> MustNodeB;

	Dijkstra(1);
	int StartToA = Dist[MustNodeA];
	int StartToB = Dist[MustNodeB];

	Dijkstra(MustNodeA);
	int AToB = Dist[MustNodeB];
	int AToN = Dist[N];

	Dijkstra(MustNodeB);
	int BToN = Dist[N];

	int result = min(
		{ StartToA + AToB + BToN,
		StartToB + AToB + AToN,
		INTMAX
		});

	if (result >= INTMAX)
		cout << -1;
	else
		cout << result;

	return 0;
}