概要

各雲にいる位置だけでなく、「今のもこもこ度」も含めて状態として管理すると、問題は非負辺重み付き最短路になります。
状態数は \(N \times K\) 個で、\(K \le 5\) と非常に小さいので、状態を増やしたグラフに対してダイクストラ法を使えば解けます。

考察

この問題の難しい点は、同じ雲にいても、現在のもこもこ度によって次の移動コストが変わることです。

たとえば雲 \(u\) にいるとして、

• 現在のもこもこ度が \(1\) なら、基本時間 \(10\) の道は \(10 \times 1 = 10\)
• 現在のもこもこ度が \(5\) なら、同じ道でも \(10 \times 5 = 50\)

となります。

つまり、「雲 \(u\) に最短で来た」という情報だけでは不十分です。
雲 \(u\) に、どのもこもこ度で来たかまで分からないと、その先の最適な行動を決められません。

素朴な方法がダメな理由

通常の最短路のように、各頂点について距離を 1 つだけ持つ方法はうまくいきません。
同じ雲でも、

• 少し遠回りしてでも小さいもこもこ度で到着した方が、
• その後の移動コストが安くなって全体最適になる

ということがあるからです。

したがって、この問題では

• 「今どの雲にいるか」
• 「今のもこもこ度はいくつか」

の組を 1 つの状態として扱う必要があります。

状態をどう作るか

状態を \((u, f)\) とします。

• \(u\) : 今いる雲
• \(f\) : 現在のもこもこ度

このとき、状態遷移は次の 2 種類です。

1. その雲のもこもこ度を採用する

雲 \(u\) に着いたとき、その雲のもこもこ度 \(F_u\) を採用できます。
これは時間が増えないので、

• \((u, f) \to (u, F_u)\) にコスト \(0\)

の遷移があると考えられます。

2. 風の通り道を移動する

現在のもこもこ度が \(f\) のとき、辺 \((u, v)\) の基本時間が \(t\) なら、移動コストは \(t \times f\) です。
したがって、

• \((u, f) \to (v, f)\) にコスト \(t \times f\)

の遷移があります。

このようにすると、すべての辺コストは非負なので、ダイクストラ法が使えます。

なぜこれで十分か

もこもこ度は常に \(1\) 以上 \(K\) 以下で、しかも \(K \le 5\) です。
つまり状態数は最大でも \(N \times 5\) 程度であり、十分扱えます。

最初は雲 \(1\) にいて、初期もこもこ度は \(F_1\) なので、開始状態は

• \((1, F_1)\)

です。

ゴールは「雲 \(N\) に到達すること」なので、最終的なもこもこ度は何でもよく、

• \(\min_f \mathrm{dist}[N][f]\)

が答えになります。

アルゴリズム

1. 状態 \((u, f)\) を「雲 \(u\) にいて、現在のもこもこ度が \(f\)」と定義する。
2. dist[u][f] を、その状態に到達する最小時間とする。
3. 初期状態は dist[1][F[1]] = 0。
4. 優先度付きキューを使ってダイクストラ法を行う。
5. 状態 \((u, f)\) を取り出したら、以下を試す。
   • 採用遷移: \((u, f) \to (u, F_u)\) をコスト \(0\) で張る
   • 移動遷移: 各辺 \((u, v, t)\) に対し、\((u, f) \to (v, f)\) をコスト \(t \times f\) で張る
6. 最後に min(dist[N][1:]) を出力する。到達不能なら -1。

コードとの対応

提出コードでは、優先度付きキューに

• (cost, node, current_fluff)

を入れています。

また、この部分が「その雲のもこもこ度を採用する」遷移です。

nf = F[u]
if nf != f and d < dist[u][nf]:
    dist[u][nf] = d
    heapq.heappush(pq, (d, u, nf))

コストが増えていないので、まさに \(0\) コスト遷移です。

そしてこの部分が「風の通り道を移動する」遷移です。

for v, t in graph[u]:
    nd = d + t * f
    if nd < dist[v][f]:
        dist[v][f] = nd
        heapq.heappush(pq, (nd, v, f))

計算量

• 時間計算量: \(O((N K + M K)\log(NK))\)
• 空間計算量: \(O(NK + M)\)

ここで \(K \le 5\) なので、実質的にはかなり軽く、十分高速です。

実装のポイント

• もこもこ度は \(1\) から \(K\) までなので、dist は K+1 列にして 1-indexed で持つと実装しやすいです。

• ダイクストラ法では、優先度付きキューから取り出した値が古い可能性があるため、

  
  if d != dist[u][f]:
    continue
  

  でスキップしています。

• 辺のコストは \(T_j \times f\) で、\(T_j\) は大きいので、他言語では 64bit 整数が必要です。Python ではそのままで問題ありません。

• ゴール時のもこもこ度は問われないので、答えは dist[N][f] の最小値です。

  ソースコード

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    it = iter(data)
    N = next(it)
    M = next(it)
    K = next(it)

    F = [0] + [next(it) for _ in range(N)]

    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = next(it)
        v = next(it)
        t = next(it)
        graph[u].append((v, t))
        graph[v].append((u, t))

    INF = 10**30
    dist = [[INF] * (K + 1) for _ in range(N + 1)]

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

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

        # Optionally adopt the current cloud's fluffiness
        nf = F[u]
        if nf != f and d < dist[u][nf]:
            dist[u][nf] = d
            heapq.heappush(pq, (d, u, nf))

        # Move along edges keeping current fluffiness
        for v, t in graph[u]:
            nd = d + t * f
            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.4-high によって生成されました。