[Gold 4] 1504 특정한 최단 경로

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

 

이 문제는 다익스트라 알고리즘을 활용한다.

 

다익스트라를 활용해서 무조건 거쳐야하는 정점까지의 최단 거리를 구한다.

이후 그 정점에서 부터 N까지의 최단 거리를 구하면 해결할 수 있다.

즉, 다익스트라 알고리즘을 3번 활용한다.

 

1번 정점에서부터 다익스트라 알고리즘을 활용하면

1번 정점애서부터 모든 정점에대한 최단 거리를 구할 수 있다.

따라서 1번 정점에서부터 u와 v정점까지의 최단 거리를 저장한다.

dijk(1);
int to_u = dist[u];
int to_v = dist[v];

 

1에서부터 u와 v정점까지의 최단 거리를 구했다면

u에서 N와 v 정점간의 최단 거리와 v에서 N간 최단 거리를 구한다.

v에서 u까지의 최단거리를 구하지 않는 이유는 양방향이기 때문

dijk(u);
int u_to_v = dist[v];
int u_to_N = dist[N];

dijk(v);
int v_to_N = dist[N];

 

이렇게 3번의 다익스트라를 통해 최단 거리를 구했다면

합을 통해 최종 결과를 만들어낸다.

int result;
result = min(INF, to_u + u_to_v + v_to_N);
result = min(result, to_v + u_to_v + u_to_N);
    
if(result >= INF)
    cout<<-1;
else
    cout<<result;

 

 

목적지가 C이고 각각의 정점을 A와 B라고 했을 때

다익스트라를 통해 1에서 A와 B까지의 최소 비용 경로를 구할 수 있다.

그후 A와 C까지의 거리와 B와 C까지의 최소 비용을 구한다.

마지막으로 1-A-C와 1-B-C 중 가장 적은 비용을 구하면 된다.

 

위 코드를 보면

첫번째 min함수는 1 - u - N 경로의 비용을 구하고 있다.

두번째 min함수는 1 - v - N 경로의 비용을 구하고 있다.

 

경로의 합 사이에 u와 v사이의 최소 비용을 더하여 u와 v를 반드시 거치도록 하였다.

 

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 200000000

int N, E, u, v;
vector<pair<int, int>> graph[801];
int dist[801];
bool visited[801];

void dijk(int st){
    // 1번에서 N번까지 이동
    // u와 v 정점을 반드시 거칠 것
    for(int i = 0;i<=N;i++)
        dist[i] = INF;

    priority_queue<pair<int, int>> pq;
    pq.push({0, st});
    dist[st] = 0;

    while(!pq.empty()){
        int cost = -pq.top().first;
        int now = pq.top().second;
        pq.pop();

        if(cost > dist[now])
            continue;

        for(int i = 0;i<graph[now].size();i++){
            int next = graph[now][i].first;
            int nCost = graph[now][i].second;

            if(dist[next] > nCost + cost){
                dist[next] = nCost + cost;
                pq.push({-dist[next], next});
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>N>>E;
    int a, b, c;
    for(int i = 0;i<E;i++){
        cin>>a>>b>>c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }
    cin>>u>>v;

    dijk(1);
    int to_u = dist[u];
    int to_v = dist[v];

    dijk(u);
    int u_to_v = dist[v];
    int u_to_N = dist[N];

    dijk(v);
    int v_to_N = dist[N];

    int result;
    result = min(INF, to_u + u_to_v + v_to_N);
    result = min(result, to_v + u_to_v + u_to_N);
    
    if(result >= INF)
        cout<<-1;
    else
        cout<<result;
}