概要

町と道からなるグラフ上で、各町を初めて訪れると体力が回復する条件下で、町1から町Nに移動する際の到着時の体力の最大値を求める問題です。

考察

この問題の重要なポイントは、同じ町を複数回訪れても回復は最初の1回のみという制約です。つまり、どの町を訪れたか（回復済みかどうか）が状態として重要になります。また、体力は回復によりいくらでも大きくなり得るため、単純なダイクストラ法ではうまく扱えません（負の辺がないが上限がないため）。

状態として「現在の町」と「これまでに訪れた町の集合（回復済みの町の集合）」の2つを組み合わせることで、問題を効率的に解くことができます。各状態での最大体力を記録しながら更新していくことで、最適解を見つけることが可能です。

アルゴリズム

ビットDP（動的計画法）を用います。状態を \((used, v)\) と表現します： - \(used\): これまでに訪れた（回復済みの）町の集合をビットマスクで表現（\(N\)ビット） - \(v\): 現在いる町（0-indexed）

各状態 \((used, v)\) に対して、その状態に到達した時点での最大体力を \(dp[used][v]\) に記録します。

初期状態は \((1<<0, 0)\) で、初期体力は \(F + R_0\) です。その後、以下のように状態を更新します： 1. 現在の状態 \((used, v)\) から、\(v\) に接続する各道 \((u, w)\) について 2. 現在の体力が \(w\) 以上なら移動可能 3. 移動後の体力は \(dp[used][v] - w\) 4. 移動先 \(u\) が未訪問（\(used\) に含まれない）なら、回復 \(R_u\) を加算 5. 新しい状態 \((new\_used, u)\) での体力がこれまでの記録より大きければ更新

これを更新がなくなるまで繰り返し、最終的に状態 \((used, N-1)\) での最大体力を答えとします。

計算量

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

\(N \leq 10\) なので、\(2^{10} = 1024\) 状態であり、十分現実的な計算量です。

実装のポイント

• 状態数は \(2^N \times N\) で、各状態の初期値を十分小さい値（\(-10^{18}\)）で初期化

• 初期状態 \((1<<0, 0)\) の体力を \(F + R[0]\) で設定

• 更新がなくなるまでループを回す（ベルマンフォード法のような更新方法）

• 各辺について双方向に移動可能なため、無向グラフとして隣接リストを構築

• 最終的に全ての状態における町 \(N-1\) の最大体力を確認

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    it = iter(data)
    N = int(next(it)); M = int(next(it)); F_val = int(next(it))
    R = [int(next(it)) for _ in range(N)]
    edges = [[] for _ in range(N)]
    for i in range(M):
        u = int(next(it)) - 1
        v = int(next(it)) - 1
        w = int(next(it))
        edges[u].append((v, w))
        edges[v].append((u, w))
        
    total_states = 1 << N
    INF = -10**18
    dp = [[INF] * N for _ in range(total_states)]
    start_state = 1 << 0
    dp[start_state][0] = F_val + R[0]
    
    updated = True
    while updated:
        updated = False
        for used in range(total_states):
            for v in range(N):
                if dp[used][v] == INF:
                    continue
                for (u, w) in edges[v]:
                    if dp[used][v] < w:
                        continue
                    new_energy = dp[used][v] - w
                    new_used = used
                    if not (used & (1 << u)):
                        new_energy += R[u]
                        new_used |= (1 << u)
                    if new_energy > dp[new_used][u]:
                        dp[new_used][u] = new_energy
                        updated = True
                        
    ans = INF
    for used in range(total_states):
        if dp[used][N-1] > ans:
            ans = dp[used][N-1]
            
    if ans == INF:
        print(-1)
    else:
        print(ans)
        
if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。