BOJ 9870 - Vacation Planning 링크
(2023.08.01 기준 G4)

문제

N개의 농장이 있고, 농장을 잇는 단방향 비행편 M개가 있다. 1~K까지의 농장은 허브이며, Q개의 여행 일정이 주어진다. 농장 a에서 시작하여 농장 b에 최소 비용을 들여서 도착하면 되는데, 무조건 허브 농장 하나는 거쳐야 한다. 이때, 주어지는 여행 일정 중 가능한 여행 일정 개수와 가능한 여행 일정들의 최소 비용 합 출력

알고리즘

플로이드 워셜

풀이

a에서 시작하여 b로 도착해야 하는데 허브 하나는 꼭 거쳐야 한다면, a -> hub, hub -> b라고 생각할 수 있다.

N이 최대 200이므로 최단 경로는 플로이드 워셜로 구한 뒤, Q개의 여행 일정마다 1부터 K까지의 농장 중 하나의 농장을 경유하는 일정이 가능한지 일일이 확인하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll inf = 1e12;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M, K, Q; cin >> N >> M >> K >> Q;

    // 간선 추가
    ll matrix[N][N]; fill(&matrix[0][0], &matrix[N - 1][N], inf);
    for (int i = 0, u, v, d; i < M; i++){
        cin >> u >> v >> d;
        matrix[--u][--v] = d;
    }

    // 플로이드 워셜
    for (int k = 0; k < N; k++){
        matrix[k][k] = 0;
        for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
            matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]);
    }

    // 유효 경로 개수, 유효 경로들의 최소 비용 합
    int valid = 0;
    ll cost = 0;
    for (int i = 0, a, b; i < Q; i++){
        cin >> a >> b; a--; b--;

        // a, 허브, b 순으로 방문할 수 있는 유효 경로를 찾아서 최소 비용 계산
        ll result = inf;
        for (int hub = 0; hub < K; hub++) if (matrix[a][hub] < inf && matrix[hub][b] < inf)
            result = min(result, matrix[a][hub] + matrix[hub][b]);

        // 최소 비용이 계산이 되었다면 유효 경로가 있다는 것이다.
        if (result < inf){
            valid++;
            cost += result;
        }
    }

    cout << valid << '\n' << cost;
}

• Python

import sys; input = sys.stdin.readline
from math import inf

N, M, K, Q = map(int, input().split())

# 간선 추가
matrix = [[inf] * N for _ in range(N)]
for _ in range(M):
    u, v, d = map(int, input().split())
    matrix[u - 1][v - 1] = d

# 플로이드 워셜
for k in range(N):
    matrix[k][k] = 0
    for i in range(N):
        for j in range(N):
            matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])

valid = cost = 0 # 유효 경로 개수, 유효 경로들의 최소 비용 합
for _ in range(Q):
    a, b = map(int, input().split())
    a -= 1; b -= 1

    # a, 허브, b 순으로 방문할 수 있는 유효 경로를 찾아서 최소 비용 계산
    result = inf
    for hub in range(K):
        if matrix[a][hub] < inf and matrix[hub][b] < inf:
            result = min(result, matrix[a][hub] + matrix[hub][b])

    # 최소 비용이 계산이 되었다면 유효 경로가 있다는 것이다.
    if result < inf:
        valid += 1
        cost += result

print(valid)
print(cost)