[1504] 특정한 최단 경로

문제 링크 : https://www.acmicpc.net/problem/1504

1504 - 특정한 최단 경로

본문

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

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

입력

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

출력

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

제한

시간 제한	메모리 제한
1sec	256MB

---

풀이

$1$번 정점부터 $N$번 정점까지의 최단거리를 구하는 방법은 여러 가지가 있다. 문제에서는 여기에 2개의 정점을 반드시 거쳐가야한다는 조건이 붙은 것. 즉, 최단경로를 $1 \rightarrow N$만 구하는 문제에서 $1 \rightarrow v1 \rightarrow v2 \rightarrow N$ 또는 $1 \rightarrow v2 \rightarrow v1 \rightarrow N$을 구하는 문제가 된다.

그래서, 사이점들에 대해서 모두 최단경로를 구해놓으면 쉽게 문제를 해결할 수 있다. 그래프가 양방향이기 때문에, $v1$과 $v2$에서 각각 모든 점에 대한 최단경로를 구해놓는다면, 결과값을 모두 더하기만 해도 답을 찾을 수 있다.

최단경로 알고리즘으로는 다익스트라를 이용했다. 시작점이 정해져있는 상황에서 다른 모든 점들까지의 최단경로를 구할 때 자주 사용하던 방법이기 때문. 정점의 개수도 많지 않기에 다른 최적화 요소를 굳이 고려하지 않았다.

• 참고 알고리즘 : 다익스트라

코드

사용 언어 : C

최종 수정일 : 2023 / 6 / 27

#include <stdio.h>

typedef char bool;
const bool true = 1;
const bool false = 0;

#define INF 987654321
#define MAX_IDX (800 + 1)

int matrix[MAX_IDX][MAX_IDX + 1];
int n, e;
int v1, v2;
int start, end;

int fromV1[MAX_IDX], fromV2[MAX_IDX];

void init() {
    for (int i = 0; i < MAX_IDX; ++i) {
        for (int j = 0; j < MAX_IDX; ++j) {
            matrix[i][j] = INF;
        }
    }
    return;
}

void dijkstra(int* dist, int v) {
    bool visit[MAX_IDX + 1] = {false};

    for (int i = 0; i <= n; ++i) {
        dist[i] = INF;
    }
    dist[v] = 0;

    int current_vertex;
    while (true) {
        current_vertex = 0;
        for (int i = 1; i <= n; ++i) {
            if (visit[i] == false && dist[i] < dist[current_vertex]) {
                current_vertex = i;
            }
        }
        if (current_vertex == 0) {
            break;
        }
        visit[current_vertex] = true;

        for (int i = 1; i <= n; ++i) {
            if (matrix[current_vertex][i] < INF) {
                if (dist[i] > dist[current_vertex] + matrix[current_vertex][i]) {
                    dist[i] = dist[current_vertex] + matrix[current_vertex][i];
                }
            }
        }
    }

    return;
}

#define min(a, b) (((a) > (b)) ? (b) : (a))
int main() {
    init();

    scanf("%d %d", &n, &e);
    while (e--) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        matrix[a][b] = matrix[b][a] = c;
    }
    scanf("%d %d", &v1, &v2);
    start = 1, end = n;

    dijkstra(fromV1, v1);
    dijkstra(fromV2, v2);

    if (fromV1[start] < INF && fromV1[end] < INF && fromV1[v2] < INF) {
        printf("%d", min(fromV1[start] + fromV1[v2] + fromV2[end], fromV2[start] + fromV1[v2] + fromV1[end]));
    } else {
        printf("-1");
    }
    return 0;
}