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

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

1504번: 특정한 최단 경로

문제요약

첫번째 노드부터 주어진 N번째 노드까지의 최단경로를 구한다. 다만, 두개의 노드가 추가로 주어지는데 이 두 노드를 반드시 경유해야 한다.

문제해결

다익스트라 알고리즘을 여러번 사용하여 문제해결을 하였다. 다만 고려사항이 몇가지가 있다.

고려사항
1. 주어진 두 노드를 지나는 순서에 따라 최단거리가 달라질 수 있다. 따라서 두가지 경우를 고려해야한다.
a : 시작 - v1 - v2 - 끝
b : 시작 - v2 - v1 - 끝
2. 끊어진 경로가 있을 수 있다. a와 b 모두 끊어진 경우에만 -1을 출력해야한다.

처음에는 a,b를 구성하는 각 경로를 구한 뒤, 더해서 a b를 만들었다. 하지만 이 때 끊어진 경로일 경우 INT_MAX가 되도록 했기 때문에 a,b가 overflow가 발생해서 최단경로가 제대로 구해지지 않았다. overflow가 발생하지 않도록 처리하는 것을 고려하지않아 많이 틀렸다.

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

#define INF 987654321
using namespace std;

int N, E;
struct edge {int to; int length;};
int dijkstra(vector< vector<edge> > graph, int source, int target);

int main(){
    cin >> N >> E;
    vector< vector<edge> > graph(N+1);
    for(int i=0; i<E; i++){
        int from, to, length;
        cin >> from >> to >> length;
        graph[from].push_back(edge{to, length});
        graph[to].push_back(edge{from, length});
    }

    int v1, v2;
    cin >> v1 >> v2;

    int dist = dijkstra(graph, v1, v2);
    if(dist == INF){
        cout << -1;
        return 0;
    } 

    int dist_a;
    int a_1 = dijkstra(graph, 1, v1);
    int a_2 = dijkstra(graph, v2, N);
    if(a_1 == INF || a_2 == INF) dist_a = INF;
    else dist_a = a_1 + a_2 + dist;

    int dist_b;
    int b_1 = dijkstra(graph, 1, v2);
    int b_2 = dijkstra(graph, v1, N);
    if(b_1 == INF || b_2 == INF) dist_b = INF;
    else dist_b = b_1 + b_2 + dist;

    if(dist_a >= INF && dist_b >= INF) cout << -1;
    else cout << (dist_a > dist_b ? dist_b : dist_a);

    // cout <<'\n'<< a_1 <<' '<< a_2 <<' '<< b_1 <<' ' << b_2 <<' ' << dist;


    return 0;
}

int dijkstra(vector< vector<edge> > graph, int source, int target){
    vector<int> min_distance(N+1, INF);
    min_distance[source] = 0;

    // (최단거리, 노드)
    set< pair<int,int> > active_virtices;
    active_virtices.insert(make_pair(0,source));

    while(!active_virtices.empty()){
        int where = active_virtices.begin()->second;

        
        if(where == target) {
            return min_distance[where];
        }

        active_virtices.erase(active_virtices.begin());
        for(auto ed : graph[where]){
            if(min_distance[ed.to] > min_distance[where] + ed.length){
                active_virtices.erase(make_pair(min_distance[ed.to], ed.to));
                min_distance[ed.to] = min_distance[where] + ed.length;
                active_virtices.insert(make_pair(min_distance[ed.to], ed.to));
            }
        }
    }

    return INF;
}