概要

この問題は、体力を持った冒険者が町と道からなるグラフを移動し、町 \(1\) から町 \(N\) へ到達する際に得られる最終体力の最大値を求めるものです。各町には一度だけ体力が回復する宿屋があり、同じ道を何回でも通れます。

考察

この問題の肝は、「訪問済みの町の集合」と「現在の体力」を状態として持つことです。

素朴な方法として、単純なBFSやDFSを行うと、同じ町を何度も行き来するループが生まれやすく、状態数が爆発してしまいます。また、体力の値も変化するため、単純に「訪れたことがあるかどうか」だけでは最適な経路を見逃してしまう可能性があります。

そこで、ビットマスクを用いてどの町を訪問したかを管理し、さらにその時点での最大体力を記録しておく必要があります。これにより、同じ「訪問状態」と「現在地」の組み合わせでも、より高い体力で到達できた場合にのみ更新を行うことができます。

具体的には、状態を (訪問済み町のビットマスク, 現在地) とし、その状態における到達可能な最大体力を記録します。ダイクストラ法のように、優先度付きキューを使って体力が多い順に探索を行うのが効果的です。

アルゴリズム

解法としては、ビットマスクを使ったダイクストラ法（または最良優先探索）を用います。

ステップ：

1. 初期状態：

   • 町 \(1\) にいる。
   • 訪問済み町のビットマスク：1 << 0（町1が立っている）。
   • 初期体力：\(F + R_1\)。

2. 状態管理：

   • visited[(mask, node)] = hp：訪問状態が mask で現在地が node のときに持てる最大体力。
   • 初期状態を優先度付きキューに入れる：(-hp, mask, node)（最大ヒープにするためにマイナスにして格納）。

3. 遷移：

   • 現在の町から移動可能な隣接町へ行く。
   • 移動に必要な体力がある場合のみ遷移可能。
   • 新しい町に初めて訪れる場合は宿屋で回復。
   • 新しい状態 (new_mask, next_node) に対して、以前より高い体力で到達できれば更新し、キューに追加。

4. 終了条件：

   • 状態が町 \(N\) に到達したら、その時点での最大体力を記録。
   • 探索終了後に、記録された町 \(N\) への最大体力を出力。到達不能なら -1。

計算量

• \(N \leq 10\) なので、ビットマスクによる訪問状態の種類は最大 \(2^{10} = 1024\)。
• 各ノードに対して最大で \(2^N\) の状態を持つので、状態数は \(O(N \cdot 2^N)\)。
• 各状態から最大 \(M\) 本の辺をたどるので、遷移数は \(O(M \cdot N \cdot 2^N)\)。
• 優先度付きキューの操作は \(O(\log(状態数)) = O(\log(N \cdot 2^N))\)

したがって、

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

実装のポイント

• 町の番号は 1-indexed なので、ビットマスクのインデックスを調整する（例: 町 \(j\) → ビット位置 \(j - 1\)）。

• 同じ状態（mask と node の組）でも、体力が異なる場合があるため、常に最大体力で更新する必要がある。

• 宿屋の回復は「初めて訪れたときのみ」なので、ビットマスクで確認する。

• ダイクストラのように、visited の値より低い体力で到達した場合は枝刈りして高速化。

  ソースコード

import heapq
import sys

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    F = int(data[idx]); idx += 1
    R = [0] * (N + 1)
    for i in range(1, N + 1):
        R[i] = int(data[idx]); idx += 1
    
    # グラフの構築
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    # 初期体力
    initial_hp = F + R[1]
    
    # dp[mask][node] = (最大体力, 実際に到達可能か)
    # maskは訪問済み町のビットマスク
    # しかし、N<=10なので、visited setを使ってDFS/BFSでも良いが、
    # 最適化のために状態を (現在地, 訪問済み集合, 体力) とする
    # BFSで探索し、(体力, mask, node)で管理する
    
    # visited[mask][node] = 到達した最大体力
    from collections import defaultdict
    visited = defaultdict(lambda: -1)
    
    # 初期状態: 町1にいて、訪問済みは {1}, 体力は F + R[1]
    mask_init = 1 << (1 - 1)
    visited[(mask_init, 1)] = initial_hp
    
    # プライオリティキュー: (-体力, mask, node)
    pq = [(-initial_hp, mask_init, 1)]
    
    max_hp_at_N = -1
    
    while pq:
        neg_hp, mask, u = heapq.heappop(pq)
        current_hp = -neg_hp
        
        if current_hp < visited[(mask, u)]:
            continue
            
        # 町Nに到着したら更新
        if u == N:
            if current_hp > max_hp_at_N:
                max_hp_at_N = current_hp
        
        # 隣接する町へ移動
        for v, cost in graph[u]:
            if current_hp >= cost:
                new_hp = current_hp - cost
                v_bit = 1 << (v - 1)
                already_visited = (mask & v_bit) != 0
                new_mask = mask | v_bit
                
                if not already_visited:
                    new_hp += R[v]
                
                if new_hp > visited[(new_mask, v)]:
                    visited[(new_mask, v)] = new_hp
                    heapq.heappush(pq, (-new_hp, new_mask, v))
    
    print(max_hp_at_N)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。