概要

この問題は、移動するたびに「現在のもこもこ度」が変化し、それが次の移動時間に影響する最短経路問題です。もこもこ度の最大値 \(K\) が非常に小さい（\(K \leq 5\)）ことに注目し、グラフの頂点に現在の状態（雲の番号ともこもこ度）を持たせることで、ダイクストラ法を適用して解くことができます。

考察

1. 状態の定義

単純なダイクストラ法では「どの雲にいるか」だけを状態として持ちますが、この問題では「現在のもこもこ度がいくつか」によって、同じ道を通る際にかかる時間が変わります。そのため、最短経路を求めるための状態を次のように定義する必要があります。 - 状態：(現在の雲の番号 \(u\), 現在のもこもこ度 \(f\))

2. もこもこ度の更新戦略

ある雲 \(i\) に到着したとき、もこもこ度を \(F_i\) に更新するか、現在の \(f\) を維持するか選べます。移動時間は \(T_j \times f\) で計算されるため、もこもこ度は小さければ小さいほど有利です。 したがって、雲 \(i\) に到着した直後の最適なもこもこ度は、常に \(\min(\text{現在の } f, F_i)\) となります。一度小さくなったもこもこ度をあえて大きくするメリットはないため、この「常に最小値を取る」という戦略が最適です。

3. \(K\) の小ささの利用

もこもこ度 \(F_i\) は \(1\) 以上 \(K\) 以下の整数で、\(K \leq 5\) と非常に小さいです。そのため、考えられる状態数は最大でも \(N \times K = 100,000 \times 5 = 500,000\) 程度に収まります。この程度の状態数であれば、ダイクストラ法で十分に高速に解くことが可能です。

アルゴリズム

ダイクストラ法を用いて、スタート地点 \((1, F_1)\) から各状態への最短時間を求めます。

1. 初期化:
   • 全ての頂点 \(u \in \{1 \dots N\}\) ともこもこ度 \(f \in \{1 \dots K\}\) の組み合わせについて、最短距離 dist[u][f] を無限大で初期化する。
   • dist[1][F_1] = 0 とし、優先度付きキューに (0, 1, F_1) を追加する。
2. 遷移:
   • キューから最小時間 \(d\) と現在の状態 \((u, f)\) を取り出す。
   • 雲 \(u\) から隣接する雲 \(v\) への道（基本時間 \(T_j\)）がある場合：
     • 移動後の合計時間：\(nd = d + T_j \times f\)
     • 移動後のもこもこ度：\(nf = \min(f, F_v)\)
     • もし \(nd < dist[v][nf]\) ならば、値を更新してキューに (nd, v, nf) を追加する。
3. 終了条件:
   • 雲 \(N\) に対応するいずれかの状態 \((N, f)\) がキューから取り出されたとき、その \(d\) が答え。
   • キューが空になっても雲 \(N\) に到達できなければ \(-1\) を出力。

計算量

• 時間計算量: \(O(MK \log (NK))\)
  • 状態数が \(NK\)、遷移（エッジ）の数が \(MK\) 本のグラフに対するダイクストラ法となります。
• 空間計算量: \(O(NK + M)\)
  • 距離配列のサイズが \(NK\)、隣接リストの保持に \(M\) の空間が必要です。

実装のポイント

• 状態の圧縮: Python等で高速化したい場合、(u, f) というタプルを管理する代わりに、ビット演算等を用いて (u << 3) | f のように1つの整数にまとめると、メモリ効率と実行速度が向上します。

• 早い段階での終了: ダイクストラ法の特性上、初めてゴールである雲 \(N\) に到達する状態が取り出された瞬間に、それが最小値であることが保証されます。

• もこもこ度の最小化: 考察で述べた通り、遷移先でのもこもこ度は min(現在のf, 到着した雲のF_v) とすれば十分です。これにより、各雲において保持すべきもこもこ度の状態を最小限に抑えられます。

  ソースコード

import sys
import heapq

def solve():
    # Read all input at once and split into tokens for fast processing
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: number of clouds, M: number of paths, K: max fluffiness
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    # F[i] is the fluffiness of cloud i+1 (0-indexed)
    F = [int(x) for x in input_data[3:3+N]]
    
    # Adjacency list for the clouds
    # adj[u] contains tuples of (neighbor_v, base_time_T)
    adj = [[] for _ in range(N)]
    it = iter(input_data[3+N:])
    for u_str in it:
        u = int(u_str) - 1
        v = int(next(it)) - 1
        t = int(next(it))
        adj[u].append((v, t))
        adj[v].append((u, t))
        
    # Dijkstra's algorithm to find the minimum travel time
    # State is (current_cloud, current_fluffiness)
    # Using a flat array for distances to improve performance in Python
    # Fluffiness f is in {1, ..., 5}, so we use (u << 3) | f as the state index
    INF = 10**18 + 7
    dist = [INF] * (N << 3)
    
    # High-level logic:
    # 1. Start at cloud 1 (index 0) with fluffiness F[0].
    # 2. To move from cloud u to cloud v via a path with base time t:
    #    - Cost = t * current_fluffiness_f
    #    - Upon arrival at v, new fluffiness becomes min(current_f, F[v])
    #      (Choosing the minimum is always optimal as t >= 1 and costs are non-negative)
    
    start_f = F[0]
    start_state = (0 << 3) | start_f
    dist[start_state] = 0
    pq = [(0, start_state)]
    
    # Optimization: Cache heapq methods
    heappush = heapq.heappush
    heappop = heapq.heappop
    
    while pq:
        d, uf = heappop(pq)
        
        # If we found a shorter path to this state already, skip it
        if d > dist[uf]:
            continue
        
        # Extract cloud index and fluffiness from the combined state
        u = uf >> 3
        
        # If we reached the goal cloud (index N-1), output the result
        # Dijkstra's ensures the first time we pop a goal state, it's the minimum cost
        if u == N - 1:
            print(d)
            return
        
        f = uf & 7
        
        # Traverse paths to neighbors
        for v, t in adj[u]:
            # The cost for the current move depends on the current fluffiness f
            nd = d + t * f
            
            # Upon arrival at cloud v, update fluffiness to min(f, F[v])
            fv = F[v]
            nf = f if f < fv else fv
            
            # Check if this path offers a shorter distance to the new state
            v_nf = (v << 3) | nf
            if nd < dist[v_nf]:
                dist[v_nf] = nd
                heappush(pq, (nd, v_nf))
    
    # If the goal cloud is unreachable
    print("-1")

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。