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

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

 

풀이)

이 문제의 경우 두 정점을 지나는 최단 경로를 구하는 문제입니다. 따라서, 다익스트라를 이용하는 문제입니다.

xnode와 ynode를  거쳐야하기때문에,

1 -> xnode -> ynode -> n

1 -> ynode -> xnode -> n

위 두가지 경로로 가는 값 중 최소 값을 출력해주면됩니다.

 

이때, 가장 실수하기 쉬운 부분은 초기에 거리값을 초기화하는 부분입니다

INF값을 범위에 맞게 잘 설정해줘야한는 점입니다.

그 이유는, 경로가 없을 경우 -1을 출력하는 부분에서 -1을 출력을 하기 위한 조건으로

보통 위의 식을 사용하는데 이때 문제가 발생할 수 있게됩니다.

 

 

두 길의 최단 거리에서 최소값을 구하는 과정에서 INF값이 세번 더해질 수도 있기 때문에 그렇습니다.

세번 더한 경우에도 int의 최댓값을 넘지 않는 범위에서 INF값을 설정해줘야합니다.

 

저는 이유를 다른 곳에서 찾으려다가 여러번 틀렸네요..

제가 생각하기에 잘 작성한 코드만 블로그에 작성하는 편인데,

혹시나 저처럼 예외가 계속 생기는 경우가 있을 것 같아 글을 남깁니다.

이번에는  그냥 예외 참고용으로 봐주셨으면 좋겠습니다..

다음은 코드입니다.

 

코드)

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

const int INF = 7e8;  // 충분히 큰 값 설정
int n, e;
vector<vector<pair<int, int>>> graph;

vector<int> dijkstra(int start) {
    vector<int> dist(n + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

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

    while (!pq.empty()) {
        int currentdist = pq.top().first;
        int currentnode = pq.top().second;
        pq.pop();

        if (currentdist > dist[currentnode]) continue;

        for (const auto& a : graph[currentnode]) {
            int nextnode = a.second;
            int nextdist = currentdist + a.first;

            if (dist[nextnode] > nextdist) {
                dist[nextnode] = nextdist;
                pq.push({ nextdist, nextnode });
            }
        }
    }

    return dist;
}

int main() {
    cin >> n >> e;
    graph.resize(n + 1);

    for (int i = 0; i < e; ++i) {
        int v1, v2, value;
        cin >> v1 >> v2 >> value;
        graph[v1].push_back({ value, v2 });
        graph[v2].push_back({ value, v1 }); // 양방향 그래프
    }

    int xnode, ynode;
    cin >> xnode >> ynode;

    vector<int> dist1 = dijkstra(1);
    vector<int> distX = dijkstra(xnode);
    vector<int> distY = dijkstra(ynode);

    int first = dist1[xnode] + distX[ynode] + distY[n];
    int second = dist1[ynode] + distY[xnode] + distX[n];

    int solve = min(first, second);

    if (solve >= INF) cout << "-1\n";
    else cout << solve << '\n';

    return 0;
}