[백준 1504번] 특정한 최단 경로 (C++)

문제링크 : https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

vector<pii> v[801];
int dist[801];
int N, E, v1, v2, a, b, c;
int s_to_v1, s_to_v2, v1_to_v2, v1_to_N, v2_to_N; //v1_to_v2 == v2_to_v1
int result=0;

void Dijkstra(int s)
{
    for(int i=1; i<=N; i++)
    {
        dist[i] = MAX;
    }
    dist[s] = 0;
    priority_queue<pii, vector<pii>,greater<pii>>pq; //최소 힙 구현 (비용 기준 작은것부터 정렬)
    pq.push({0, s}); //비용 시작점

    while(!pq.empty())
    {
        auto [cost, cur] = pq.top();
        pq.pop();

        if(dist[cur] < cost) continue;

        for(int i=0; i<v[cur].size(); i++)
        {
            auto [next, ncost] = v[cur][i];
            if(dist[next] > ncost + cost)
            {
                dist[next] = ncost + cost;
                pq.push({ncost + cost, next});
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> E;
    for(int i=0; i<E; i++)
    {
        cin >> a >> b >> c;
        v[a].push_back({b, c}); //양방향 그래프
        v[b].push_back({a, c});
    }
    
    cin >> v1 >> v2;

    Dijkstra(1);
    s_to_v1 = dist[v1]; //1 ~ v1 거리
    s_to_v2 = dist[v2]; //1 ~ v2 거리

    Dijkstra(v1);
    v1_to_v2 = dist[v2]; //v1 ~ v2 거리 == v2 ~ v1 거리
    v1_to_N = dist[N]; //v1 ~ N 거리

    Dijkstra(v2);
    v2_to_N = dist[N]; // v2 ~ N 거리

    result = min(s_to_v1 + v1_to_v2 + v2_to_N, s_to_v2 + v1_to_v2 + v1_to_N);
    cout << ((result >= MAX || v1_to_v2 >=MAX) ? -1 : result); 
    return 0;
}

다익스트라 알고리즘을 살짝 응용한 문제이다.

해당 문제에서 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하도록 하였으므로 주어진 루트는 아래 2가지인 것을 알 수 있다.

1 -> v1 -> v2 -> N
1 -> v2 -> v1 ->N

 

따라서 다익스트라 알고리즘을 여러번 돌려서 다음과 같은 거리를 구할 수 있다.

<시작점 1>
1 ~ v1 까지의 거리
1 ~ v2 까지의 거리

<시작점 v1>
v1 ~ v2 까지의 거리 (v2 ~ v1까지의 거리와 같다)
v1 ~ N 까지의 거리

<시작점 v2>
v2 ~ N 까지의 거리

 

이를 조합하면 아래 2가지 거리를 구할 수 있다.

(1 ~ v1) + (v1 ~ v2) + (v2 ~ N) 

(1 ~ v2) + (v2 ~ v1) [==v1 ~ v2] + (v1 ~ N)

 

이렇게 구한 거리 중에서 작은 값을 출력해주면 된다.

여기서 예외처리를 해줘야하는 부분이 있는데 여기서 나는 MAX를 98765431로 두고 풀었는데 이러면 result의 값이 int 값을 초과하는 경우가 발생한다.

 

더하는 값이 3가지 인데, 여기서 두 가지 모두 사용하는 거리인 v1_to_v2가 MAX값이 넘어가면 이는 해당 거리로 이동이 불가능하다는 것이다.

따라서 앞에 거리인 ~ v1과 뒤의 거리인 v2 ~ 도 이동이 불가능하다는 것을 알 수 있다.

이로 인해 중간 값이 MAX이면 앞 뒤값도 MAX 이므로  3*MAX의 값은 int 값을 초과하여 int 값을 쓸꺼면 v1_to_v2가 MAX일때 -1 을 출력해줌으로써 예외처리를 해주어야 한다.

 

아니면 result와 관련 변수들을 int가 아닌 long long으로 선언해줘야 한다.

이를 몰라서 다 풀어놓고 엄청 틀리다가 백준 질문게시판의 예제를 돌리다가 쓰레기값이 출력되는 것을 보고 알 수 있었다.