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

1504번: 특정한 최단 경로

다익스트라

---

1. 문제 해결 아이디어

 

반드시 방문해야 하는 정점이 2개 주어진다.

 

예를 들어 1번 정점에서 4번 정점으로 가야하는데 2, 3번 정점을 반드시 거쳐야 한다고 하자

첫 번째로 1 -> 2 -> 3 -> 4 순으로 정점을 방문할 수 있다.

위 순서는 각 정점이 방문된 시점을 순서대로 나열한 것에 불과하다.

1에서 2, 2에서 3, 3에서 4로 가는 최단 거리를 구하기 위해서 중간에 다양한 정점을 방문할 수 있다.

두 번째로 1 -> 3 -> 2 -> 4 순으로 정점을 방문할 수 있다.

 

같은 정점을 여러번 방문할 수 있고 이미 지나온 간선을 여러번 거쳐갈 수 있기 때문에 다익스트라 알고리즘을 활용해서 첫 번째 케이스로 

1 -> 2로 가는 최단거리, 2 -> 3으로 가는 최단거리, 3 -> 4로 가는 최단거리를 각각 구해준다.

이때 위 3개의 경로 중 하나라도 갈 수 없는 상황이 생긴다면 1 -> 2 -> 3 -> 4 경로는 사용할 수 없다.

 

1 -> 3 -> 2 -> 4 경로도 똑같이 구할 수 있다.

 

그리고 두 경로 중 거리가 짧은 경로를 선택하면 답이 된다.

---

2.  코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, E, V1, V2;
vector<pii > adj[801];
vector<int> dist;
 
void input(){
    int a, b, c;
    cin >> N >> E;
    for(int i = 0; i < E; i++){
        cin >> a >> b >> c;
        adj[a].push_back({c, b});
        adj[b].push_back({c, a});
    }
    cin >> V1 >> V2;
}
 
int dijkstra(int st, int ed){
    dist = vector<int>(N+1, INF);
    priority_queue<pii, vector<pii >, greater<pii > > que;
    que.push({0, st});
    
    dist[st] = 0;
    
    while(!que.empty()){
        int now = que.top().second;
        int cost = que.top().first;
        que.pop();
        
        if(cost > dist[now]) continue;
        
        for(int i = 0; i < adj[now].size(); i++){
            int next = adj[now][i].second;
            int next_cost = adj[now][i].first + cost;
            
            if(next_cost < dist[next]){
                dist[next] = next_cost;
                que.push({next_cost, next});
            }
        }
    }
    
    return dist[ed];
}
 
void solve(){
    int res1, res2;
    int a1 = dijkstra(1, V1);
    int a2 = dijkstra(V1, V2);
    int a3 = dijkstra(V2, N);
    if(a1 == INF || a2 == INF || a3 == INF) res1 = INF;
    else res1 = a1 + a2 + a3;
    
    int b1 = dijkstra(1, V2);
    int b2 = dijkstra(V2, V1);
    int b3 = dijkstra(V1, N);
    if(b1 == INF || b2 == INF || b3 == INF) res2 = INF;
    else res2 = b1 + b2 + b3;
    
    if(res1 == INF && res2 == INF) cout << -1;
    else cout << min(res1, res2);
}
 
int main(){
    fasti
    input();
    solve();
    
    return 0;
}