BOJ 20313 - 출퇴근 링크
(2024.03.30 기준 G3)

문제

$1$번부터 $N$번까지 번호가 붙은 $N$개의 건물 중에서, $A$번 건물에 거주 중이며 $B$번 건물로 매일 출퇴근한다.

$N$개의 건물을 잇는 $M$개의 양방향 도로가 주어진다. 그리고 최대 $K$번 마법을 사용할 수 있으며, 마법을 $k$번 사용하면 모든 $i$에 대해 $i$번 도로의 가중치가 $T_{i,k}$로 된다.

마법을 적절히 활용해서 회사에 도착하는 최단 시간 출력

알고리즘

전형적인 다익스트라 문제

풀이

$K$가 최대 $100$인 것에서 거리 배열을 $K$개 나타낼 수 있음을 알 수 있다.

$dist(i, k)$를 마법을 적절히 $k$번까지 사용했을 때, $A$번에서 $i$번까지 이동하는 최단 거리라고 정의해보자.

$i$번에서 간선으로 연결되어 있는 $j$번으로 간다고 했을 때, 마법을 $k-1$번 사용한 상태의 간선을 이용할 수 있는가? 불가능하다. 마법을 사용하지 않거나, 한 번만 사용하거나 아님 $K-k$번 사용은 가능하다. 즉, 현재 마법을 사용한 횟수를 줄일 수는 없고, 그대로 유지하거나 횟수를 증가시키기만 가능하다.

그럼 결국 $k \le k' \le K$를 만족하는 모든 $k'$에 대해 $dist(j, k') > dist(i, k) + T_{i, k'}$를 확인하는 다익스트라를 진행하면 해결할 수 있다.

코드

• C++

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

typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<ll, int, int> tlii;

const ll inf = LLONG_MAX;

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

    int N, M, A, B; cin >> N >> M >> A >> B;

    vector<pii> G[N + 1]; // 인접 리스트로 도착 정점과 간선 인덱스 저장
    vector<ll> E[M]; // 각 간선의 마법 횟수에 따른 가중치를 저장
    for (int i = 0, U, V, T; i < M; i++){
        cin >> U >> V >> T;
        E[i].push_back(T); // i번 간선의 마법 0번 때의 가중치
        G[U].push_back({V, i});
        G[V].push_back({U, i});
    }

    int K; cin >> K;
    for (int _ = 0; _ < K; _++) for (int i = 0, T; i < M; i++){
        cin >> T;
        E[i].push_back(T); // i번 간선의 마법 K번 때의 가중치
    }

    priority_queue<tlii, vector<tlii>, greater<tlii>> pq;
    pq.push({0, A, 0}); // 거리, 정점, 마법 횟수
    // dist(i, k) : 마법 k번 때, A번 정점에서 i번 정점까지 최단 거리
    ll dist[N + 1][K + 1]; fill(&dist[1][0], &dist[N][K + 1], inf);
    dist[A][0] = 0;

    // 다익스트라
    while (!pq.empty()){
        auto [t, u, k] = pq.top(); pq.pop();
        if (dist[u][k] < t) continue;
        for (auto [v, i]: G[u])
            // 현재 마법 k번을 사용했으므로, 앞으로 마법을 k~K번 사용한 상태로 바꿀 수 있다.
            // 즉, 마법 k번 미만 사용한 상태로 바꿀 수 없다.
            for (int k_ = k, t_; k_ <= K; k_++){
                t_ = E[i][k_];
                if (dist[v][k_] > t + t_){
                    dist[v][k_] = t + t_;
                    pq.push({dist[v][k_], v, k_});
                }
            }
    }

    ll ans = inf;
    for (int k = 0; k <= K; k++) ans = min(ans, dist[B][k]);
    cout << ans;
}

• Python (PyPy3)

import sys; input = sys.stdin.readline
from math import inf
from heapq import heappop, heappush

N, M, A, B = map(int, input().split())

G = [[] for _ in range(N + 1)] # 인접 리스트로 도착 정점과 간선 인덱스 저장
E = [[] for _ in range(M)] # 각 간선의 마법 횟수에 따른 가중치를 저장
for i in range(M):
    U, V, T = map(int, input().split())
    E[i].append(T) # i번 간선의 마법 0번 때의 가중치
    G[U].append((V, i))
    G[V].append((U, i))

K = int(input())
for _ in range(K):
    T = list(map(int, input().split()))
    for i in range(M):
        E[i].append(T[i]) # i번 간선의 마법 K번 때의 가중치

pq = [(0, A, 0)] # 거리, 정점, 마법 횟수
# dist(i, k) : 마법 k번 때, A번 정점에서 i번 정점까지 최단 거리
dist = [[inf] * (K + 1) for _ in range(N + 1)]
dist[A][0] = 0

# 다익스트라
while pq:
    t, u, k = heappop(pq)
    if dist[u][k] < t:
        continue
    for v, i in G[u]:
        # 현재 마법 k번을 사용했으므로, 앞으로 마법을 k~K번 사용한 상태로 바꿀 수 있다.
        # 즉, 마법 k번 미만 사용한 상태로 바꿀 수 없다.
        for k_ in range(k, K + 1):
            t_ = E[i][k_]
            if dist[v][k_] > t + t_:
                dist[v][k_] = t + t_
                heappush(pq, (dist[v][k_], v, k_))

print(min(dist[B]))