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

www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)

 

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

 

 

풀이

이번 문제에선 길이 양방향이다!! 단방향이라고 착각하고 풀어서 제대로 답이 나오지 않았었다.

1에서 출발하여 n까지 이동하는 경로 중 v1과 v2를 반드시 지나는 최단 경로를 구해야한다.

1) 1 -> v1 -> v2 -> n

2) 1 -> v2 -> v1 -> n

이렇게 두 가지 방식으로 이동할 수 있다.

따라서 다익스트라 알고리즘을 여러번 실행하여 문제에서 요구하는 최단거리를 구하였다.

 

우선 출발위치를 1로 하여 다익스트라 알고리즘을 실행하여 1부터 각각의 정점까지의 거리를 배열 dist[]에 저장되도록 하였다.

그런뒤

1) v1을 먼저 거치는 경우엔 dist[v1]을 변수 v1_v2에,

2) v2를 먼저 거치는 경우엔 dist[v2]를 변수 v2_v1에 저장한다.

 

1)의 경우엔 v1을 시작점으로 하는 다익스트라 알고리즘을 다시 실행하여 v1에서부터 v2까지의 최단 거리(dist[v2])를 구해 v1_v2에 더하고, 또 한번 다익스트라 알고리즘을 실행해 v2에서부터 n까지의 최단거리(dist[n])을 v1_v2에 더해준다.

이때 하나라도 경로가 없는 경우가 있다면 in_v1을 1로 만들어주어 유효하지 않은 경로라는 것을 표시해 준다.

2)의 경우에도 마찬가지로 실행하며 유효한 경로인지 확인하면 된다.

 

1)과 2) 모두 유효한 경우엔  v1_v2와 v2_v1 중 더 작은 것을 출력하고

둘중 하나만 유효한 경우엔 유효한 경로의 비용을 출력하고

모두 유효하지않은 경우엔 -1을 출력하면되는 문제이다.

 

#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int dist[801];
vector<vector<pair<int, int>>> way;
priority_queue<pair<int, int>> pq; //비용, 위치

void dijkstra(int s, int n);

int main(void){
    int n, e, v1, v2;
    int a, b, c;
    int v1_v2;
    int v2_v1;
    int in_v1=0, in_v2=0;
    
    
    
    scanf("%d %d", &n, &e);
    
    
    way.resize(n+1);
    for(int i=0; i<e; i++){
        scanf("%d %d %d", &a, &b, &c);
        way[a].push_back(make_pair(b, c));
        way[b].push_back(make_pair(a, c));
    }
    scanf("%d %d", &v1, &v2);
    
    
    dijkstra(1, n);
    //v1->v2
    v1_v2 = dist[v1];
    //v2->v1
    v2_v1 = dist[v2];
    if(dist[v1] == -1 ){
        in_v1 = 1;
    }
    if(dist[v2] == -1){
        in_v2 = 1;
    }
   
    //v1->v2
    dijkstra(v1, n);
    v1_v2 +=dist[v2];
    if(dist[v2] == -1 ){
        in_v1 = 1;
    }
    dijkstra(v2, n);
    v1_v2 +=dist[n];
    if(dist[n] == -1 ){
        in_v1 = 1;
    }
    

    
    //v2->v1
    dijkstra(v2, n);
    v2_v1 +=dist[v1];
    if(dist[v1] == -1 ){
        in_v2 = 1;
    }
    dijkstra(v1, n);
    v2_v1 +=dist[n];
    if(dist[n] == -1 ){
        in_v2 = 1;
    }

    
    if(in_v1 != 1 && in_v2 !=1){
        if(v1_v2 < v2_v1)
            printf("%d\n", v1_v2);
        else
            printf("%d\n", v2_v1);
    }
    
    else if(in_v1 == 1 && in_v2 == 1){
        printf("-1\n");
    }
    
    else if(in_v1 == 1 && in_v2 == 0){
        printf("%d\n", v2_v1);
    }
    else if(in_v1 == 0 && in_v2 == 1){
        printf("%d\n", v1_v2);
    }
}

void dijkstra(int s, int n){
    int here, cost;
    int there, there_cost;
    
    for(int i=1; i<=n; i++){
        dist[i] = -1;
    }
    
    dist[s] = 0;
    
    pq.push(make_pair(0, s));
    
    while(!pq.empty()){
        cost = -pq.top().first;
        here = pq.top().second;
        pq.pop();
        if(dist[here] < cost)
           continue;
        
        for(int i=0; i<way[here].size(); i++){
            there = way[here][i].first;
            there_cost = cost + way[here][i].second;
            
            if(dist[there] == -1){
                dist[there] = there_cost;
                pq.push(make_pair(-there_cost, there));
            }
            else if( dist[there] > there_cost){
                dist[there] = there_cost;
                pq.push(make_pair(-there_cost, there));
            }
        }
    }
}