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

✏️ 문제 링크

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

1504번: 특정한 최단 경로

 

 

✏️ 문제 설명 (더보기 클릭 👆🏻)

 

✏️ 문제 풀이

문제 조건을 보면 1번에서 N번을 가려고하는데 한번 이동했던 정점은 물론, 한번 이동했던 간선들도 다시 이동할 수 있지만 v1, v2정점을 반드시 거치는 경로를 찾아야한다. 

그러면 가능한 경로는 1 -> V1 -> V2 -> N / 1 -> V2 -> V1 -> N이다. 

찾아야하는 최단경로는 아래와 같다. 

1. 시작점을 1로 해서 V1 과 V2 까지 가는 최단 경로를 각각 찾아준다. 

1 -> V1, 1-> V2

2. V1에서 V2 혹은 V2에서 V1을 가는 최단 경로를 찾아준다. 

V1-> V2 or V2-> V1

3. V1에서 N, V2 에서 N으로 가는 경로를 찾아준다. 

V1-> N, V2 -> N

 

//start to v1, v2
int StoV1=dijkstra(1, v1);
int StoV2=dijkstra(1, v2);
    
//v1 to v2, v1 to N
int V1toV2=dijkstra(v1, v2);
int V1toN=dijkstra(v1, N);
    
//v2 to N
int V2toN=dijkstra(v2, N);

 

 

✏️ 문제 코드

#include <bits/stdc++.h>

using namespace std;
using pii=pair<int, int>;

#define INF 987654321
#define MAX 801

int N, E; 
vector<pii> vec[MAX];


int dijkstra(int start, int dest){
    vector<int> dist(N+1, INF);
    
    priority_queue<pii> pq; pq.push({0,start});
    dist[start]=0;
    while(!pq.empty()){
        pii t=pq.top(); pq.pop();
        int cur=t.second; int d=t.first*-1;
        
        if(dist[cur]<d) continue;
        
        for(int i=0; i<vec[cur].size(); i++){
            int nxt=vec[cur][i].first;
            int nxt_dist=vec[cur][i].second+d;
            if(nxt_dist<dist[nxt]){
                dist[nxt]=nxt_dist;
                pq.push({nxt_dist*-1, nxt});
            }
        }
    }
    
    
    return dist[dest];
}

int main(){
    cin>>N>>E;
    while(E--){
        int a,b,c; cin>>a>>b>>c;
        vec[a].push_back({b, c});
        vec[b].push_back({a, c});
    }
    int v1, v2; cin>>v1>>v2;
    
    //start to v1, v2
    int StoV1=dijkstra(1, v1);
    int StoV2=dijkstra(1, v2);
    
    //v1 to v2, v1 to N
    int V1toV2=dijkstra(v1, v2);
    int V1toN= dijkstra(v1, N);
    
    //v2 to N
    int V2toN=dijkstra(v2, N);
    
    int res=INF;
    res=min(res, StoV1+V1toV2+V2toN);
    res=min(res, StoV2+V1toV2+V1toN);
    
    if(res>=INF || V1toV2==INF) cout<<-1;
    else cout<<res;
    
    return 0;
}

 

 

 

 ⭐ if feedback and question : comment please⭐