[BOJ-1504]특정한 최단 경로

이 문제는 

정점이 n 개가 (v1 ,v2, .... , vn)

있을 때 정점1->정점N 최단경로를 구하는 문제이다.  

이때 ! 특정한 조건이 있다.

임의의 정점 2개가 주어지는데(Va, Vb)

정점1->정점N 까지 진행하며, 정점a 와 정점b를 무조건! 지나서 가야한다는 점이다. 

그러면? 다익스트라 알고리즘을 적용하여서

정점1에서 정점a 정점b 정점n 으로 가는 방법 1

정점1에서 정점b 정점a 정점n 으로 가는 방법 2

위 2가지만 다익스트라로 체크해주면 되는 문제이다!

그냥 다익스트라를 여러번 쓰는 문제!

만약 경로가 존재하지 않는다면? -1을 출력한다. 

#include<cstdio>
#include<functional>
#include<queue>
#include<vector>
#include<utility>
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
using namespace std;
 
typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
 
const int INF = 666666666;
 
VI vertex;
VPII edge[888];
int n,e;
int dijkstra(int src, int dst){
    vertex = VI(n+1, INF);
    vertex[src] = 0;    
    priority_queue<PII, VPII, greater<PII> > Q;
    Q.push(mp(0, src));
    while(!Q.empty()){
        int here = Q.top().second;
        int dist = Q.top().first;
        Q.pop();
        if(vertex[here] < dist) continue;
 
        for(auto iter = edge[here].begin() ; iter != edge[here].end() ; iter++){
            PII p = *iter;
            int there = p.first;
            int cost = p.second;
            if(vertex[there] > vertex[here] + cost){
                vertex[there] = vertex[here] + cost;
                Q.push(mp(vertex[there], there));
            }
        }
    }
    return vertex[dst];
}
 
int main(){
    scanf("%d%d", &n, &e);    
    for(int i = 0 ; i < e ; i++){
        int u,v,w;
        scanf("%d%d%d", &u, &v, &w);
        edge[u].pb(mp(v,w));
        edge[v].pb(mp(u,w));
    }
    // src : 1 , dst : n
    // v1 , v2
    int v1, v2;
    scanf("%d%d", &v1, &v2);
 
    int src_v1 = dijkstra(1, v1);
    int src_v2 = dijkstra(1, v2);
    int v1_v2 = dijkstra(v1, v2);
    int v2_v1= dijkstra(v2, v1);
    int v1_n= dijkstra(v1, n);
    int v2_n= dijkstra(v2, n);
    
    int src_12_n = INF; 
    if(src_v1 != INF && 
        v1_v2 != INF &&
        v2_n != INF){
            src_12_n = src_v1 + v1_v2 + v2_n;
    }
    int src_21_n = INF;
    if(src_v2 != INF &&
        v2_v1 != INF &&
        v1_n != INF){
            src_21_n = src_v2 + v2_v1 + v1_n;
    }
 
    if(src_21_n != INF){
        printf("%d", (src_21_n > src_12_n)? src_12_n : src_21_n);
    }else{
        printf("-1");
    }
 
    return 0;
}