概要

「現在のもこもこ度」まで含めて状態管理する最短路問題です。
頂点だけでなく (雲, 現在のもこもこ度) を1つの状態としてグラフを作り直し、ダイクストラ法で最短時間を求めます。

考察

この問題の難しさは、移動コストが「今持っているもこもこ度」に依存する点です。
つまり、同じ雲 \(u\) にいても、現在のもこもこ度 \(f\) が違えば次の移動コストが変わります。

---

まず、よくある誤りとして

• dist[u] = 雲uへの最短時間 だけを持つ

という通常の最短路をするとWAになります。
なぜなら、雲 \(u\) に「少し遅く」着いても、その時のもこもこ度が小さければその後の移動が有利になり、最終的にゴールへは速くなる可能性があるからです。

---

そこで重要な気づきは次です：

• 状態を \((u, f)\)（雲 \(u\) にいて現在もこもこ度が \(f\)）とする
• この状態空間で最短路を解く

遷移は2種類あります。

1. 採用遷移（その場で変更）
   雲 \(u\) に到着したら、もこもこ度を \(F_u\) に変更できる。
   これはコスト \(0\) の遷移： $\( (u, f) \to (u, F_u) \)$

2. 移動遷移（辺を通る）
   辺 \((u,v,t)\) を現在もこもこ度 \(f\) で通ると $\( (u, f) \to (v, f),\quad \text{cost}=t \times f \)\( （実装では \)f\( を 0-index にしているので、実際は \)t \times (f+1)$）

これで「重み非負の最短路」になり、ダイクストラ法がそのまま使えます。
制約で \(K \le 5\) と小さいため、状態数は \(N \times K\) で十分現実的です。

アルゴリズム

1. もこもこ度 \(F_i\) を 0-index 化（\(1..K \to 0..K-1\)）。
2. dist[u][f] を「状態 \((u,f)\) への最短時間」で初期化。
3. 初期状態は雲1にいてもこもこ度 \(F_1\) なので
   dist[0][F[0]] = 0。
4. 優先度付きキューでダイクストラ：
   • 取り出した状態 \((u,f)\) から
     • 採用遷移：\((u,f) \to (u,F_u)\)（コスト0）
     • 各隣接辺 \((u,v,t)\) に対し移動遷移：\((u,f)\to(v,f)\)（コスト \(t \times (f+1)\)）
   • 改善したら push
5. 最後に min(dist[N-1][f]) を答えとする。到達不能なら -1。

計算量

• 状態数：\(N \times K\)
• 各状態からの遷移：採用1本 + 隣接辺本数ぶん
  全体ではだいたい \(O((NK + MK)\log(NK))\)

したがって
- 時間計算量: \(O((N K + M K)\log(NK))\) - 空間計算量: \(O(NK + MK)\)（dist と状態グラフ相当。実装上の隣接リスト本体は \(O(N+M)\)）

実装のポイント

• もこもこ度を 0-index にすると配列管理が楽（移動コストは f+1 を掛ける）。

• ダイクストラの定番として、if d != dist[u][f]: continue で古いキュー要素を捨てる。

• 辺重みは最大で \(10^9 \times 5\)、経路長も大きくなり得るので、Pythonのintで安全に扱う（INF = 10**30 など十分大きく）。

  ソースコード

import sys
import heapq

def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    F = list(map(int, input().split()))
    F = [x - 1 for x in F]  # 0-indexed fluffiness

    g = [[] for _ in range(N)]
    for _ in range(M):
        u, v, t = map(int, input().split())
        u -= 1
        v -= 1
        g[u].append((v, t))
        g[v].append((u, t))

    INF = 10**30
    # dist[node][f] = min time to be at node with current fluffiness f (0..K-1)
    dist = [[INF] * K for _ in range(N)]

    start_f = F[0]
    dist[0][start_f] = 0
    pq = [(0, 0, start_f)]  # (cost, node, fluff)

    while pq:
        d, u, f = heapq.heappop(pq)
        if d != dist[u][f]:
            continue

        # Option: adopt this cloud's fluffiness
        fu = F[u]
        if d < dist[u][fu]:
            dist[u][fu] = d
            heapq.heappush(pq, (d, u, fu))

        # Move along edges with current fluffiness f
        mult = f + 1
        for v, t in g[u]:
            nd = d + t * mult
            if nd < dist[v][f]:
                dist[v][f] = nd
                heapq.heappush(pq, (nd, v, f))

    ans = min(dist[N - 1])
    print(ans if ans < INF else -1)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.3-codex によって生成されました。