BOJ 1504번 : 특정한 최단 경로

평범함 다익스트라 문제와 다르게 두 정점을 반드시 통과해야 하고, 양방향 그래프인 조건을 모두 충족해야 한다.

단방향 그래프를 표현할 때에는 (start, end, cost)를 v[start]({end, cost})에만 추가하면 되지만,

양방향 그래프를 표현해야 하므로 v[end]({start,cost}) 또한 추가해주어야 한다.

 

다음은 두 정점을 반드시 통과해야 하는 조건이다.

반드시 통과해야 하는 두 정점을 p1, p2라고 할 경우

1. p1-p2 사이의 최단 거리

2. min( (start-p1 최단 거리)+(end-p2 최단 거리) , (start-p2 최단 거리)+(end-p1 최단 거리))

를 구한 후 더해주면 된다.

 

start-p1-p2-p1-end 로 가는 방식이 최단 거리일 수도 있지만, 2번 조건을 충족할 경우 이 또한 만족 할 수 있다.

 

결과 값이 max 값 이상일 경우 조건을 만족하는 최단 거리가 없다는 의미이므로 -1을 출력하면 된다.

 

<소스코드>

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
 
using namespace std;
 
int N,E;
vector<pair<int,int>> v[801];
int p1,p2;
 
long long dijkstra(int start, int end){
    priority_queue<pair<int,int>> pq; // cost , node
    vector<long long> dis(N+1,INT_MAX);
    dis[start] = 0;
    pq.push(make_pair(0, start));
    
    while(!pq.empty()){
        
        int cur = pq.top().second;
        int cdis = pq.top().first*-1;
        pq.pop();
        
        if(dis[cur] < cdis) continue;
        
        for(int i = 0; i<v[cur].size(); i++){
            int nxt = v[cur][i].first;
            int nxt_cost = v[cur][i].second;
            
            if(nxt_cost + cdis < dis[nxt]){
                dis[nxt] = nxt_cost + cdis;
                pq.push(make_pair(dis[nxt] * -1, nxt));
            }
            
        }
        
    }
    return dis[end];
    
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin>>N>>E;
    
    for(int i = 0; i<E; i++){
        int a,b,c;
        cin>>a>>b>>c;
        v[a].push_back(make_pair(b, c));
        v[b].push_back(make_pair(a, c));
    }
    
    cin>>p1>>p2;
    
    int start = 1;
    int end = N;
    
    long long ans = dijkstra(p1, p2);
    ans += min(dijkstra(start, p1)+dijkstra(end, p2),dijkstra(start, p2)+dijkstra(end, p1) );
    
    if(ans >= INT_MAX)
        cout<< "-1" <<endl;
    
    else
        cout<<ans<<endl;
    
}
 

 

<문제>

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

1504번: 특정한 최단 경로