백준 1504 특정한 최단 경로 c++ [컴공과고씨]

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

1504번: 특정한 최단 경로

 

문제 간단 정리

방향성 없는 그래프 주어짐.

1번 부터 n 정점까지 최단 거리로 이동함.

조건은 임의로 주어진 두 정점은 반드시 통과해야함.

그리고 한 번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이용가능.

1번에서 n정점으로 이동할 때 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 길이를 출력하라

경로가 없으면 -1을 출력.

 

문제 해결 방법 

다익스트라를 활용하여 풀면 쉽게 풀 수 있는 문제이다.

다익스트라를 모른다면 https://hagisilecoding.tistory.com/134 한번 보고 오면 이해가 쉽다.

다익스트라를 이용해서 무조건 거쳐야하는 정점까지 최단 거리를 구한후 다시 그 정점 부터 n정점까지

최단거리를 구해 주면 쉽게 해결할 수 있다.

즉, 다익스트라 함수를 총 3번을 써야한다. 

 

예를 들어 목적지 C가 있고 거치는 정점 A B가 있다고 하자. 

그럼 다익스트라를 이용해서 출발점 부터 A 와 B까지 최단거리를 구할 수 있다.

그 후 A 부터 C 까지 거리한번 B 부터 C까지 거리를 구해준다.

그 후 출발점-A-C 가 가까운지 출발점-B-C가 가까운지 비교해준다.

이때 전부 갈 수 없는 길이면 -1을 출력한다.

 

전체 코드

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int INF = 98765432;
vector<pair<int, int>> v[802];
int dist[803];
void bfs(int a)
{
    memset(dist, INF, sizeof(dist));
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push(make_pair(0, a));
    dist[a] = 0;
    while (!q.empty())
    {
        int sum_distance = q.top().first;
        int x = q.top().second;
        q.pop();
        
        if(dist[x] < sum_distance)
            continue;
        for (int i = 0; i < v[x].size(); i++){
            int nx = v[x][i].first;
            int ncost = sum_distance + v[x][i].second;
 
            if(dist[nx] > ncost){
                q.push({ncost, nx});
                dist[nx] = ncost;
            }
        }
    }
}
int mn(int a, int b){
    if(a<b)
        return a;
    else
        return b;
}
int main(){
    int n, e;
    cin >> n >> e;
    int a1,a2,a3;
    for (int i = 0; i < e; i++){
        cin >> a1 >> a2 >> a3;
        v[a1].push_back({a2, a3});
        v[a2].push_back({a1, a3});
    }
    int dt1, dt2;
    cin >> dt1 >> dt2;
    
    bfs(1);
    int To_dt1 = dist[dt1];
    int To_dt2 = dist[dt2];
 
    bfs(dt1);
    int dt1_To_dt2 = dist[dt2];
    int dt1_To_n = dist[n];
 
    bfs(dt2);
    int dt2_To_n = dist[n];
 
    int result;
 
    result = mn(INF, To_dt1 + dt1_To_dt2 + dt2_To_n);
    result = mn(result, To_dt2 + dt1_To_dt2 + dt1_To_n);
    if(result >= INF)
        cout << -1;
    else
        cout << result;
    return 0;
}