백준 1504번, 특정한 최단 경로(C, C++)

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

1504번: 특정한 최단 경로

#include<iostream>
#include<vector>
#include<queue>
#define INF 100000000

using namespace std;
vector<pair<int, int>> a[801];

int dist[801];
int N;
int E;
void dijkstra(int start){
      for(int i = 0; i <= N; i++){
        dist[i] = INF;
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[start] = 0;
    pq.push(make_pair(0, start));
    while(!pq.empty()){
        int cur = pq.top().second;
        int cost = pq.top().first;
        pq.pop();
        if(dist[cur] < cost){
            continue;
        }
        for(int i = 0; i < a[cur].size(); i++){
            int next = a[cur][i].first;
            int ncost = a[cur][i].second;
            if(dist[next] > ncost + cost){
                dist[next] = ncost + cost;
                pq.push({dist[next], next});
            }
        }
    }
}

int main(){
    cin >> N >> E;
    int x;
    int y;
    int z;
    int v1;
    int v2;
    int ans = INF;

  

    for(int i = 0; i < E; i++){
        cin>>x>>y>>z;
        a[x].push_back({y, z});
        a[y].push_back({x, z});
    }
    cin>>v1>>v2;

    dijkstra(1);
    int first_tov1 = dist[v1];
    int first_tov2 = dist[v2];

    dijkstra(v1);
    int v1tov2 = dist[v2];
    int v1toN = dist[N];
    
    dijkstra(v2);
    int v2toN = dist[N];

    ans = min(ans, first_tov1 + v1tov2 + v2toN);
    ans = min(ans, first_tov2 + v1tov2 + v1toN);

    if(v1tov2 == INF || ans == INF){
        cout<<-1;
    }else{
        cout<<ans;
    }



    return 0;
}

 위 그림은 정점이 5개이며 간선이 6개인 상황을 예시로 나타낸 것 입니다.

 1번 정점부터 시작해서 2번 정점과 3번 정점을 무조건 지나면서 5번 정점에 도달하는 최소 값을 구해야합니다.

 

1번 정점에서 2번 정점으로 가는 길이를 cost 1이라고 표현했습니다.

dist[2] = INF였던 것이 cost1으로 갱신되고, 힙의 구조를 가지고 있는 우선순위 큐에 dist[2]와 2번 정점의 위치가 들어갑니다.

dist[3]은 cost2로 갱신되며 마찬가지로 우선 순위 큐에 dist[3]과 3번 정점의 위치가 들어갑니다.

 

앞서 말했던 대로 2번과 3번 정점을 무조건적으로 지나야합니다.

그렇지만 기본적으로 구현된 다익스트라를 작동하게되면 2번 정점에서 5번 정점으로 가는 것보다 2번 정점에서 3번 정점, 4번 정점을 들려 5번으로 가는 cost의 합이 작아야만 2번과 3번정점을 무조건적으로 들립니다.

 

따라서 1->2->3->4->5로 들리거나 1->3->2->5로 가는 방법의 경우밖에 없습니다.

 

 

1부터 시작되도록 다익스트라 함수를 실행하게되면

1에서 2로 가는 비용인 dist[2]의 값과 1에서 3으로 가는 dist[3] 비용을 알 수 있습니다.

 

 

시작점이 3번 정점으로 되도록 다익스트라 함수를  실행합니다.

3번 정점에서 2번 정점으로 가는 길이가 dist[2]에 저장이 됩니다.

 

2번 정점부터 5번 정점까지 가는 다익스트라를 실행하게되면 dist[5]가 갱신되며

1->3->2->5로 가는 길이가 나오게됩니다.

 

위 그림을 이용하여 1 - > 2 - > 3 - 4 - > 5로 가는 방법과 1->3->2->5 가는 길이의 최소 값을 구합니다.

 

문제 조건에서 왔던 길을 되돌아가는 것도 허용이 된다고 합니다. 왜냐하면 3번 정점에서 2번 정점을 갈 때 사용 되는 다익스트라 함수는

2->3가는 경우뿐만 아니라 3->1->2로 가는 방법을 비교하여 최소 거리로 갔고 만약에 3 - > 1 - > 2로 가는 방법을 다익스트라 함수가 택하게 되었다면 맨 처음에 우리가 실행한 1번 정점에서 3번 정점으로 가는 다익스트라 함수가 길을 건너왔을 수도 있기 때문입니다.

(1번 ->3번 정점으로 가는 경우와 1번 ->2번정점->3번 정점으로 가는 경우에 최소 길이가 누가 될 지 모르기 때문에 불확실하다는 표현을 사용했습니다.)