백준 1504번 - 특정한 최단 경로

www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

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

 

문제에서 확인해야 하는 조건들

 

1. 방향성이 없는 그래프 -> 무방향 그래프, 즉 양방향 그래프가 된다. (입력받을 때 처리)

 

2. 임의로 주어진 두 정점은 반드시 통과해야 한다. -> 두 정점을 거쳐서 가야함

 

3. 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동 가능 -> 각각의 중간 정점에 가서 새롭게 다익스트라 돌리기

 

 

해결 방법

 

반드시 정해진 두 정점을 거쳐서 간다면 경우의 수는 총 2가지가 나올 수 있다.

 

정해진 두 정점을 A, B라 한다면

 

1번 경우 : 시작점 -> A -> B -> 도착점

2번 경우 : 시작점 -> B -> A -> 도착점

 

사실 이게 끝이다. 

 

각각의 최단거리는 당연히 다익스트라로 구해주면 된다.

 

이렇게 해서 총 구해야 할 것은 5개이다. (아래의 X -> Y는 X부터 Y까지의 최단경로를 의미한다)

 

시작점 -> A, 시작점 -> B    => 이 두 개는 다익스트라 한 번으로 구할 수 있다. (다익스트라의 정의를 생각해보자)

A -> B ( == B -> A )         => 양방향 그래프이기 때문에 A -> B나 B -> A는 똑같다. 즉 다익스트라 한번으로 구할 수 있음

A -> 도착점, B -> 도착점    => 양방향 그래프이기 때문에 A -> 도착점 == 도착점 -> A이다.

즉 도착점에서 시작해서 다익스트라를 사용하면 도착점 -> A, 도착점 -> B를 구할 수 있고, 이는 결국 도착점 -> A와 도착점 -> B와 같다.

 

이렇게 다익스트라를 3번 사용해서 정답을 구할 수 있다.

 

마지막으로 출력 조건만 잘 설정해주면 끝!

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int, int> pii;
 
vector<pii>g[808];
int dis[808];
bool check[808];
 
void dijkstra(int x) {
    dis[x] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push(make_pair(0, x));
    while (!pq.empty()) {
        int now = pq.top().second;
        int wei = pq.top().first;
        pq.pop();
        if (check[now] == true)continue;
        check[now] = true;
        if (dis[now] < wei) continue;
        for (int i = 0; i < g[now].size(); i++) {
            int next = g[now][i].first;
            int ww = g[now][i].second;
            if (dis[now] + ww < dis[next]) {
                dis[next] = dis[now] + ww;
                pq.push(make_pair(dis[next], next));
            }
        }
    }
}
 
void init() {
    memset(dis, 127, sizeof(dis));
    memset(check, false, sizeof(check));
}
 
void solve(int start) {
    init();
    dijkstra(start);
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n, m, k, a, b, u, v, e;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> e;
        g[u].push_back(make_pair(v, e));
        g[v].push_back(make_pair(u, e));
    }
    cin >> a >> b;
    int s_a, s_b, a_b, a_e, b_e;
    init();
    int INF = dis[0];
    solve(1); // (시작점 -> a 시작점 -> b) 한번에 구할 수 있음
    s_a = dis[a]; s_b = dis[b];
    solve(a); // a -> b 최단 거리 (양방향 그래프이기 때문에 b -> a와 같음)
    a_b = dis[b];
    solve(n); // a -> 도착점, b->도착점 (양방향 그래프이기 때문에 a -> n == n -> a )
    a_e = dis[a]; b_e = dis[b];
    // 출력조건 -> 경우의 수는 2가지 밖에 없기 때문에, 중간 중간 경로가 있는지 없는지 판단
    if (a_b == INF) cout << -1 << "\n";
    else {
        if (s_a == INF || b_e == INF) {
            if (s_b == INF || a_e == INF) cout << -1 << "\n";
            else cout << s_b + a_b + a_e << "\n";
        }
        else {
            if (s_b == INF || a_e == INF) cout << s_a + a_b + b_e << "\n";
            else cout << min(s_b + a_b + a_e, s_a + a_b + b_e) << "\n";
        }
    }
}

 

다익스트라 알고리즘을 이해하고 있다면 어렵지 않은 문제였다.