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

1504번: 특정한 최단 경로

cpp

#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(해당노드 최단거리값+가중치, 인접노드 최단거리값)

 

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

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