[Baekjoon/C++] 1504번 - 특정한 최단 경로

[백준] Baekjoon Online Judge

문제로 이동

 

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

 

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

 

---

풀이

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define INF 200000000

vector<pair<int, int>> edge[801];
vector<int> dist[3];

void dijkstra(int start, int idx);

void dijkstra(int start, int idx) {
    priority_queue<pair<int, int>> q;

    q.push({ 0, start });
    dist[idx][start] = 0;

    while (!q.empty()) {
        int now = q.top().second;
        int w = -q.top().first;

        q.pop();

        if (dist[idx][now] < w) continue;

        for (pair<int, int> ii : edge[now]) {
            int nw = w + ii.first;

            if (nw < dist[idx][ii.second]) {
                dist[idx][ii.second] = nw;
                q.push({ -nw, ii.second });
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int N, E; // 정점의 개수 N, 간선의 개수 E
    int v1, v2;

    cin >> N >> E;
    for (int i = 0; i < E; i++) {
        int a, b, c;
        cin >> a >> b >> c;

        edge[a].push_back({ c, b });
        edge[b].push_back({ c, a });
    }
    cin >> v1 >> v2;

    for (int i = 0; i < 3; i++)
        dist[i].resize(N + 1, INF);

    dijkstra(1, 0);
    dijkstra(v1, 1);
    dijkstra(v2, 2);

    int result = min(dist[0][v1] + dist[1][v2] + dist[2][N], dist[0][v2] + dist[2][v1] + dist[1][N]);

    if (result >= INF) 
        cout << "-1\n";
    else
        cout << result << '\n';

    return 0;
}

 데이크스트라 알고리즘으로 문제를 풀었다.

 

    dijkstra(1, 0);
    dijkstra(v1, 1);
    dijkstra(v2, 2);

    int result = min(dist[0][v1] + dist[1][v2] + dist[2][N], dist[0][v2] + dist[2][v1] + dist[1][N]);

    if (result >= INF) 
        cout << "-1\n";
    else
        cout << result << '\n';

 1에서 N까지 가는데 무조건 2개의 정점을 지나가야 한다. 이는 즉, 1 > v1 > v2 > N이나 1 > v2 > v1 > N 순으로 이동해야 함을 의미한다. 그러므로 1과 v1, v2를 시작점으로 데이크스트라를 돌려 3개의 시작점에 대한 각 정점의 최단거리를 구하도록 했다.

 그 후 1 > v1 > v2 > N와 1 > v2 > v1 > N 경로의 거리를 구하고, 둘 중 거리가 짧은 것으로 result를 초기화하고, 이를 출력하도록 했다. 이때 result가 INF보다 크거나 같으면 1에서 N으로 가는 경로가 없는 것이기에 -1을 출력하도록 했다.