概要

\(N\) 個の雲と \(M\) 本の風の通り道からなるグラフ上で、「現在のもこもこ度」によって辺のコストが変わる最短経路問題です。もこもこ度の種類数 \(K\) が最大 \(5\) と小さいことを利用し、状態を拡張したダイクストラ法で解きます。

考察

普通の最短路との違い

通常のダイクストラ法では、各ノードへの最短距離だけを管理すれば十分です。しかし本問題では、同じ雲に到着しても「現在のもこもこ度」が異なれば、その後の移動コストが変わります。

例: 雲 \(A\) にコスト \(10\) で到着しもこもこ度 \(1\) の場合と、コスト \(12\) で到着しもこもこ度 \(1\) の場合では前者が良いのは明らかです。しかし、コスト \(10\) でもこもこ度 \(5\) の場合と、コスト \(12\) でもこもこ度 \(1\) の場合では、後者の方がその後の移動コストが小さくなるため、最終的に有利になる可能性があります。

つまり、ノードだけでなく「現在のもこもこ度」も状態として持つ必要があります。

\(K\) が小さいことの活用

もこもこ度は \(1\) 以上 \(K\) 以下の整数で、\(K \leq 5\) です。したがって状態を \((\text{雲の番号}, \text{現在のもこもこ度})\) と定義しても、状態数は \(N \times K\) で最大 \(500{,}000\) 程度に収まり、十分高速に処理できます。

アルゴリズム

状態拡張ダイクストラ法を使います。

1. 状態の定義: \((u, f)\) = 「雲 \(u\) にいて、現在のもこもこ度が \(f\) である」
2. 初期状態: \((1, F_1)\) でコスト \(0\)
3. 遷移: 状態 \((u, f)\) から辺 \((u, v, T)\) を通ると、コスト \(T \times f\) で雲 \(v\) に到着する。到着後、次の2つの状態に遷移できる：
   • \((v, f)\)：もこもこ度を維持する
   • \((v, F_v)\)：到着した雲のもこもこ度を採用する
4. 答え: \(\min_{f=1}^{K} \text{dist}(N, f)\)

これは通常のダイクストラ法と同じ枠組みで、ノード数が \(N \times K\) に増えた重み付きグラフの最短路問題として解けます。

具体例

\(K = 3\) のグラフで雲 \(A\)（もこもこ度\(3\)）→ 雲 \(B\)（もこもこ度\(1\)）→ 雲 \(C\) と進む場合： - \(A \to B\): もこもこ度 \(3\) なのでコスト \(T_{AB} \times 3\) - \(B\) に到着後、もこもこ度を \(1\) に変更 - \(B \to C\): もこもこ度 \(1\) なのでコスト \(T_{BC} \times 1\)

低いもこもこ度の雲を経由することで、以降の移動コストを抑える戦略が重要です。

計算量

• 時間計算量: \(O(MK \log(NK))\)
  • 状態数は \(O(NK)\)、各辺について最大 \(K\) 種の状態から遷移が発生し、ダイクストラの優先度付きキューの操作に \(\log\) がかかります。
• 空間計算量: \(O(NK + M)\)
  • 距離配列に \(O(NK)\)、隣接リストに \(O(M)\)

実装のポイント

• 状態のインデックス化: dist[u * K + fi] のように1次元配列で管理すると高速です（fi は \(f - 1\) で \(0\)-indexed）。

• 重複遷移の回避: 到着した雲のもこもこ度 \(F_v\) が現在のもこもこ度 \(f\) と同じ場合、「維持」と「採用」の遷移先が同一なので、片方だけ処理すれば十分です。

• Python での高速入力: sys.stdin.buffer.read() を用いて一括読み込みすることで、大量入力でもTLEを回避しています。

• 答えの出力: 雲 \(N\) にどのもこもこ度で到着しても良いので、\(\text{dist}(N, 1), \text{dist}(N, 2), \ldots, \text{dist}(N, K)\) の最小値を取ります。

  ソースコード

import heapq
import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    
    F = [0] * N
    for i in range(N):
        F[i] = int(data[idx]); idx += 1
    
    adj = [[] for _ in range(N)]
    for j in range(M):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        t = int(data[idx]); idx += 1
        adj[u].append((v, t))
        adj[v].append((u, t))
    
    INF = float('inf')
    # dist[node * K + f_index]
    size = N * K
    dist = [INF] * size
    
    start_fi = F[0] - 1
    dist[0 * K + start_fi] = 0
    
    pq = [(0, 0, start_fi)]
    
    while pq:
        d, u, fi = heapq.heappop(pq)
        
        uid = u * K + fi
        if d > dist[uid]:
            continue
        
        f = fi + 1  # actual mokumoku degree
        
        for v, t in adj[u]:
            cost = d + t * f
            vid_keep = v * K + fi
            if cost < dist[vid_keep]:
                dist[vid_keep] = cost
                heapq.heappush(pq, (cost, v, fi))
            
            fv = F[v] - 1
            if fv != fi:
                vid_adopt = v * K + fv
                if cost < dist[vid_adopt]:
                    dist[vid_adopt] = cost
                    heapq.heappush(pq, (cost, v, fv))
            # if fv == fi, already handled above
    
    base = (N - 1) * K
    ans = min(dist[base: base + K])
    if ans == INF:
        print(-1)
    else:
        print(ans)

main()

---

この解説は claude4.6opus-thinking によって生成されました。