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

1504번: 특정한 최단 경로

#include <iostream>
#include <climits>
#include <list>
#include <queue>
using namespace std;

const int Infinite = INT_MAX;

typedef pair<int, int> node;

int N, E;
list<pair<int, int>> Neighbors[801];

int Distance[801];
priority_queue<node, vector<node>, greater<node>> SQ;

int Dijkstra(int Start, int End)
{
	for (int i = 1; i <= N; ++i)
	{
		Distance[i] = Infinite;
	}

	Distance[Start] = 0;
	SQ.emplace(0, Start);
	while (!SQ.empty())
	{
		int CurIdx = SQ.top().second;
		int CurCst = SQ.top().first;
		SQ.pop();

		if (CurCst > Distance[CurIdx])
		{
			continue;
		}

		for (const pair<int, int>& N : Neighbors[CurIdx])
		{
			int NewCst = Distance[CurIdx] + N.second;
			if (NewCst < Distance[N.first])
			{
				Distance[N.first] = NewCst;
				SQ.emplace(NewCst, N.first);
			}
		}
	}

	return Distance[End];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> N >> E;
	for (int i = 0; i < E; ++i)
	{
		int A, B, C;
		cin >> A >> B >> C;

		Neighbors[A].emplace_back(B, C);
		Neighbors[B].emplace_back(A, C);
	}

	int X, Y;
	cin >> X >> Y;

	int SolA = Infinite, SolB = Infinite;

	int Dst1, Dst2, Dst3;

	Dst1 = Dijkstra(1, X);
	Dst2 = Dijkstra(X, Y);
	Dst3 = Dijkstra(Y, N);

	if (Dst1 != Infinite && Dst2 != Infinite && Dst3 != Infinite)
	{
		SolA = Dst1 + Dst2 + Dst3;
	}

	Dst1 = Dijkstra(1, Y);
	Dst2 = Dijkstra(Y, X);
	Dst3 = Dijkstra(X, N);

	if (Dst1 != Infinite && Dst2 != Infinite && Dst3 != Infinite)
	{
		SolB = Dst1 + Dst2 + Dst3;
	}

	if (SolA == Infinite && SolB == Infinite)
	{
		cout << -1;
		return 0;
	}

	cout << min(SolA, SolB);
}

---

 

다익스트라 알고리즘 구현과 경유지의 경유 순서에 따라 최소값이 달라지는 점을 캐치하는 것이 중요한 문제입니다.

 

일반적인 다익스트라 알고리즘 풀이 과정입니다.

1. 인접 리스트로 그래프 구현

2. 최단 거리 배열 초기화 - 출발 노드가 0, 나머지는 무한

3. 최단 거리 배열에서 값이 가장 작은 노드 선택 - 우선순위큐 사용

4. 해당 노드의 인접 노드들의 최단 거리값 업데이트 - min(해당노드 최단거리값+가중치, 인접노드 최단거리값)

 

알고리즘 구현 후, 문제에서 제시한 두 경유지 중 먼저 방문할 경유지를 선택해서

각 경우 마다 최소경로를 모두 구하고 그 중 더 작은 값을 선택하면 됩니다.