概要

町 \(1\) から町 \(N\) へ移動する際、各町の宿屋（初回訪問時のみ体力回復）を活用しながら、到着時の体力を最大化する問題です。\(N \leq 10\) という小さな制約を活かし、「どの町を訪問済みか」をビットマスクで管理する状態探索で解きます。

考察

重要な気づき

1. 宿屋の回復は各町につき1回のみ：同じ町を何度訪れても回復は初回だけです。したがって、「どの町を既に訪問したか」という情報が体力の計算に不可欠です。

2. 同じ道・同じ町を何度でも通れる：通常の最短路問題とは異なり、遠回りしてでも多くの宿屋を回って体力を回復した方が有利になる場合があります。

3. 素朴な最短路ではダメな理由：通常のダイクストラ法では「最小コスト」を求めますが、この問題では回復量があるため「体力最大化」が目的です。また、訪問済みの町の集合によって同じ町にいても体力が異なるため、単に「町ごとの最大体力」を管理するだけでは不十分です。

例：町 \(A\) を経由して町 \(B\) に着いた場合と、町 \(C\) を経由して町 \(B\) に着いた場合では、今後訪問できる宿屋が異なるため、現時点で体力が低くても将来的に有利になり得ます。

1. \(N \leq 10\) という制約：訪問済み集合をビットマスクで表すと \(2^{10} = 1024\) 通り。状態数は \(N \times 2^N \leq 10 \times 1024 = 10240\) と十分小さいです。

状態の定義

状態を （現在の町, 訪問済み集合のビットマスク） と定義し、各状態で達成可能な最大体力を管理します。

アルゴリズム

ビットマスク付き最大体力探索（ダイクストラ法の最大化版） を用います。

1. 初期状態: 町 \(0\)（0-indexed で町 \(1\)）、訪問済みマスク \(= \{0\}\)（ビット \(0\) が立つ）、体力 \(= F + R_1\)。

2. 優先度付きキュー: 体力が大きい状態を優先的に処理するため、体力の符号を反転して最小ヒープを最大ヒープとして利用します。

3. 遷移: 現在の町 \(u\)（体力 \(s\)、訪問マスク \(mask\)）から隣接する町 \(v\) へ辺コスト \(w\) で移動するとき：

   • \(s \geq w\) でなければ移動不可
   • 新しい体力 \(s' = s - w\)
   • 町 \(v\) が未訪問なら \(s' \mathrel{+}= R_v\)、マスクも更新
   • \(s'\) が best[v][new_mask] より大きければ更新してキューに追加

4. 答え: 町 \(N-1\) に到達した全状態の中での体力の最大値。到達不可能なら \(-1\)。

計算量

• 状態数: \(N \times 2^N\)

• 各状態からの遷移: 最大 \(N-1\) 本の辺

• 優先度付きキューの操作: 各状態につき \(O(\log(N \cdot 2^N))\)

• 時間計算量: \(O(N^2 \cdot 2^N \cdot \log(N \cdot 2^N))\)

  • \(N = 10\) のとき約 \(10^5\) 程度の状態数で十分高速

• 空間計算量: \(O(N \cdot 2^N)\)（best テーブルと優先度付きキュー）

実装のポイント

• 最大ヒープの実現: Python の heapq は最小ヒープなので、体力を負にしてキューに入れることで最大体力優先の探索を実現しています。

• 枝刈り: キューから取り出した状態の体力が best テーブルの値より小さい場合はスキップします。これにより不要な探索を大幅に削減できます。

• 町 \(N\) に到着しても探索を続ける: 町 \(N\) を経由して他の宿屋を回り、再度町 \(N\) に戻る方が体力が高くなる可能性があるため、町 \(N\) 到着時点で探索を打ち切らないことが重要です。

• 0-indexed への変換: 入力は 1-indexed ですが、ビットマスクの管理のしやすさから 0-indexed に変換しています。

  ソースコード

import heapq
from itertools import combinations

def solve():
    N, M, F = map(int, input().split())
    R = list(map(int, input().split()))
    
    adj = [[] for _ in range(N)]
    for _ in range(M):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        adj[u].append((v, w))
        adj[v].append((u, w))
    
    # State: (current_town, frozenset of visited towns)
    # We want to maximize stamina at town N-1
    # N <= 10, so visited set can be bitmask (up to 2^10 = 1024)
    
    # We use a modified Dijkstra-like approach but maximizing stamina
    # State: (town, visited_mask)
    # For each state, track maximum stamina achievable
    
    # Use priority queue with negative stamina (max-heap via min-heap)
    
    initial_stamina = F + R[0]
    initial_mask = 1 << 0  # visited town 0
    
    # best[town][mask] = max stamina known
    best = [[- 1] * (1 << N) for _ in range(N)]
    best[0][initial_mask] = initial_stamina
    
    # Max-heap: (-stamina, town, mask)
    pq = [(-initial_stamina, 0, initial_mask)]
    
    ans = -1
    
    while pq:
        neg_stam, u, mask = heapq.heappop(pq)
        stamina = -neg_stam
        
        # If we already found a better way to this state, skip
        if stamina < best[u][mask]:
            continue
        
        if u == N - 1:
            ans = max(ans, stamina)
            # Don't stop - might find better through different visited sets
            # But we can continue exploring from town N-1 too
        
        for v, w in adj[u]:
            if stamina < w:
                continue
            
            new_stam = stamina - w
            new_mask = mask
            
            if not (mask & (1 << v)):
                # First visit to v
                new_stam += R[v]
                new_mask = mask | (1 << v)
            
            if new_stam > best[v][new_mask]:
                best[v][new_mask] = new_stam
                heapq.heappush(pq, (-new_stam, v, new_mask))
    
    print(ans)

solve()

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