[백준][C++] 1504번: 특정한 최단 경로 <201>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

1504번: 특정한 최단 경로

나의 생각

일단 최단거리를 구하는 문제니 다익스트라 알고리즘이 떠올랐다.

문제는 특정한 지점 A, B 를 반드시 지나쳐야 한다는 점 이다!

 

가능한 case는 다음과 같다.

1) start -> A -> B -> end

2) start -> B -> A -> end

 

따라서 다익스트라는 3번만 실행해주면 된다.

맨 처음 start를 기준으로 Dijkstra(start)를 실행하면 start -> A, start -> B 로의 최소경로의 값을 구할 수 있다.

 

이후 Dijkstra(A) 를 통해 A -> B 의 최소 경로를 찾는다. 이는 B -> A 를 구한것고 동일한 값이다.

왜냐하면, 양방향 그레프 이기 때문이다! 어느 쪽으로 가든 비용을 동일하게 된다.

 

마지막으로 end를 기준으로 Dijkstra(end)를 실행하면 end -> A, end -> B 의 최소경로를 구할 수 있다.

 

이렇게 각각의 값을 다 구한 이후에 1,2 번 case처럼 값을 합하여 비교해주면 된다!

 

INF가 최대 3번 더해져서 오버플로우가 발생할 수 있다. 이럴 경우 -1을 출력해주도록 마지막에 처리해 준다.

 

나의 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX 801
#define INF 987654321

int N, E;
int A, B;
int dist[200001];
vector<pair<int, int>> adj[MAX];

void Dijkstra(int start) {
    for (int i = 0; i <= N; i++) dist[i] = INF;
    priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

    pq.push({0, start});
    dist[start] = 0;

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

        for(auto e : adj[now]) {
            int nextCost = e.first;
            int nv = e.second;
            if(cost + nextCost < dist[nv]) {
                dist[nv] = cost + nextCost;
                pq.push({dist[nv], nv});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> E;
    int a, b, c;
    for(int i = 0; i < E; i++) {
        cin >> a >> b >> c;
        adj[a].push_back({c, b});
        adj[b].push_back({c, a});
    }
    cin >> A >> B;

    Dijkstra(1);
    int OneToACost = dist[A];
    int OneToBCost = dist[B];

    Dijkstra(A);
    int AtoBCost = dist[B];

    Dijkstra(N);
    int AtoEndCost = dist[A];
    int BtoEndCost = dist[B];

    int res = min(OneToACost + AtoBCost + BtoEndCost, OneToBCost + AtoBCost + AtoEndCost);
    if(res > INF || res < 0) {
        cout << -1;
    }else{
        cout << res;
    }

    return 0;
}