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

이번 문제는 다익스트라 알고리즘을 사용하였습니다. 

단 이번에는 기존의 다익스트라 알고리즘을 사용하는 것에서, 알아야할 조건은 다음과 같습니다.

 

1. 그래프는 양방향 그래프이다.

2. 1에서 n까지 가는데에, v1,v2을 지나쳐야 한다.

3. 단 2번에서 v1 or v2 or n이 연결될 수 없이 고립되어 있다면 -1을 출력해라.

 

1번의 구현은 매우 쉬우니 넘어가고,
2번과 3번의 경우는 다익스트라 알고리즘을 다음과 같이 나눠서 구현하였습니다.

int temp1 = solve(1, x);// 1 to x
    int temp2 = solve(1, y);// 1 to y
    int temp3 = solve(x, y);// x to y
    int temp4 = solve(x, n);// x to n
    int temp5 = solve(y, n);// y to n
    int answer = min(temp1 + temp3 + temp5,temp2 + temp3+temp4);// min(1->x->y->n,1->y->x->n)
    if (answer >= INF || answer <0) cout << -1;
    //INF가 3개이상 더해질시 음수가 되므로 음수도 고려
    else cout<<answer;

아래의 전체코드를 보면 아시겠지만, INF는 987654321으로서 3번 합해질시 오버플로우가 일어나 음수가 되게 됩니다.

따라서 answer을 INF이상일 때와 음수일 때 두가지를 모두 고려하여 예외처리를 하였습니다.

 

#import<bits/stdc++.h>

using namespace std;
#define endl '\n'
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second

const int INF = 987654321;

vector<pii> weight[801];
int n,m,x,y;

int solve(int start,int end){
    priority_queue<pii,vector<pii>,greater<pii>> pq;//max heap
    vector<int> dist(n+1,INF);
    dist[start] = 0;
    pq.push({0,start});//0 is distance
    while(!pq.empty()){
        int cur = pq.top().ss;//출발지점에서부터 (pq에 저장된것중) 가장 큰 거리를 가진 노드
        int cur_distance =  pq.top().ff;//출발지점에서 그 노드까지의 거리.
        pq.pop();
        if(dist[cur] < cur_distance)continue;
        //만약 저장되어있는 거리보다 더 클시에는 최단거리가 아니므로 스킵
        for(int i =0;i<weight[cur].size();i++){
            int next = weight[cur][i].ss;
            int next_distance = (weight[cur][i].ff) + cur_distance;
            // 시작 노드에서 cur과 연결된 노드까지의 거리값 초기화
            if(next_distance <= dist[next]){
                //그 거리가 새로 연결된 노드가 기존 저장값보다 작다고 되어있을시 초기화
                pq.push({next_distance,next});
                dist[next] = next_distance;
            }
        }
    }
    return dist[end];
}
int main() {
    fast_io;
    cin>>n>>m;///node,edge
    for(int i =0;i<m;i++){
        int start,end,distance;
        cin>>start>>end>>distance;
        weight[start].pb({distance,end});
        weight[end].pb({distance,start});
    }//양방향
    cin>>x>>y;
    int temp1 = solve(1, x);// 1 to x
    int temp2 = solve(1, y);// 1 to y
    int temp3 = solve(x, y);// x to y
    int temp4 = solve(x, n);// x to n
    int temp5 = solve(y, n);// y to n
    int answer = min(temp1 + temp3 + temp5,temp2 + temp3+temp4);// min(1->x->y->n,1->y->x->n)
    if (answer >= INF || answer <0) cout << -1;
    //INF가 3개이상 더해질시 음수가 되므로 음수도 고려
    else cout<<answer;
    return 0;
}

링크 : www.acmicpc.net/problem/1504