概要

「各町の回復は初回だけ」という条件のため、訪れた町の集合（どこで回復済みか）を状態として持つ部分集合DPを行い、町 \(N\) 到着時の体力最大値を求めます。

考察

重要な気づき

• 体力が増えるのは 各町につき最初の1回だけ なので、「どの町を初訪問済みか」が本質的な状態になります。
• 同じ町・同じ道を何度でも通れるため、経路の長さ自体は無限に伸び得ますが、回復イベントは高々 \(N\) 回しか起きません。
  よって「訪問済み集合（ビット集合）」を使えば有限状態に落とせます（\(N \le 10\) なので \(2^N\) が現実的）。

素朴な探索が難しい理由

• 「今いる町」と「体力」だけで最大化しようとすると、回復済みかどうかで将来が変わるため情報が不足してWAになります。
• 「今いる町」「体力」「回復済み集合」で探索すると状態数は有限ですが、体力は上限がなく（回復で増え得る）、単純な最短路/最長路の枠に乗りません。

どう解決するか

• 状態を「回復済み集合 \(mask\)」と「現在位置 \(v\)」にし、
  その状態で到達可能な体力の最大値をDPで管理します。
• ただし「訪問済みの町の中を移動する（回復なし）」は何回でもできるので、
  各 \(mask\) について 訪問済み部分グラフ内での最小移動コスト（最短距離）を使い、
  「同じ \(mask\) のまま行ける限り、どの町にどれだけ体力を残して到達できるか」を一気に計算します。

アルゴリズム

状態定義

• \(best[mask][v]\)：
  「初回訪問済みの町集合が \(mask\)（= 回復を受けた町集合）」で、現在地が町 \(v\) のときの 到達可能な体力の最大値。
  到達不可能なら \(-1\)。

初期状態： - 町1は出発時点で初訪問扱いなので
\(best[1 \ll 0][0] = F + R_1\)

1) 同一 \(mask\) 内での“自由移動”（回復なし）の反映

\(mask\) に含まれる町だけを使って移動する限り、回復は増えません（もう回復済みのため）。

そこで、 - \(mask\) に含まれる頂点集合を \(S\) とし、 - 「\(S\) の頂点のみを中継点としてよい」最短距離 \(dist_S[i][j]\) を求めます。

これは「誘導部分グラフ上の全点対最短路」なので、\(|S|\le 10\) を活かして Floyd–Warshall を \(S\) 上だけ回します。

最短距離が得られれば、同じ \(mask\) のまま - \(s \to u\) にコスト \(dist_S[s][u]\) で移動できるなら体力は \(best[mask][s] - dist_S[s][u]\)。

よって同一 \(mask\) 内での到達可能体力は [ best’[mask][u] = \max_{s \in S} (best[mask][s] - dist_S[s][u]) ] で一発更新できます（最短距離の三角不等式により、この更新は追加で繰り返す必要がありません）。

2) 新しい町へ入る遷移（回復が発生）

次に、まだ \(mask\) に含まれていない町 \(x\) を 初めて訪れる遷移を考えます。

辺 \((a, b, w)\) について、 - \(a \in mask\), \(b \notin mask\) かつ \(best'[mask][a] \ge w\) なら - \(a \to b\) で体力 \(w\) を消費し、到着直後に \(R_b\) 回復するので [ best[mask \cup {b}][b] = \max\left(best[mask \cup {b}][b],\; best’[mask][a] - w + R_b\right) ] 逆向きも同様に行います。

3) 答え

町 \(N\) を含む任意の \(mask\) について \(best[mask][N]\) の最大値が答え。
一度も到達できなければ \(-1\)。

計算量

• 時間計算量: \(O\!\left(2^N \cdot (N^3 + M)\right)\)
  （各 \(mask\) で部分集合上Floyd–Warshallが最大 \(O(N^3)\)、遷移で辺をなめて \(O(M)\)）
• 空間計算量: \(O(2^N \cdot N + N^2)\)

実装のポイント

• 回復済み集合をビットで管理します（町 \(i\) を \(i-1\) bit）。

• 同一 \(mask\) 内の移動は「回復なし」なので、最短距離さえ分かれば体力最大は一括で更新できます： [ \max_s (E_s - dist[s][u]) ]

• Floyd–Warshallは「\(mask\) に含まれる頂点だけ」ループすることで十分です（\(N \le 10\) なのでコピーして回しても間に合います）。

• 到達不能状態は \(-1\) で管理し、比較時に弾くと実装が楽です。

  ソースコード

import sys

def main() -> None:
    input = sys.stdin.readline
    N, M, F = map(int, input().split())
    R = list(map(int, input().split()))

    INF = 10**18
    g = [[INF] * N for _ in range(N)]
    for i in range(N):
        g[i][i] = 0

    edges = []
    for _ in range(M):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        edges.append((u, v, w))
        g[u][v] = g[v][u] = w

    nodes_list = [[] for _ in range(1 << N)]
    masks_by_size = [[] for _ in range(N + 1)]
    for mask in range(1 << N):
        nodes = [i for i in range(N) if (mask >> i) & 1]
        nodes_list[mask] = nodes
        masks_by_size[mask.bit_count()].append(mask)

    best = [[-1] * N for _ in range(1 << N)]
    start_mask = 1 << 0
    best[start_mask][0] = F + R[0]

    for size in range(1, N + 1):
        for mask in masks_by_size[size]:
            if (mask & start_mask) == 0:
                continue
            cur = best[mask]
            if max(cur) < 0:
                continue

            nodes = nodes_list[mask]

            # Floyd-Warshall on induced subgraph (only nodes in mask as intermediates/endpoints)
            dist = [row[:] for row in g]
            for k in nodes:
                dk = dist[k]
                for i in nodes:
                    di = dist[i]
                    aik = di[k]
                    if aik == INF:
                        continue
                    base = aik
                    for j in nodes:
                        nj = base + dk[j]
                        if nj < di[j]:
                            di[j] = nj

            # Closure inside the same mask: move within visited towns without gaining rewards
            orig = cur
            new = orig[:]
            for u in nodes:
                best_u = new[u]
                for s in nodes:
                    bs = orig[s]
                    if bs < 0:
                        continue
                    d = dist[s][u]
                    if d == INF or bs < d:
                        continue
                    cand = bs - d
                    if cand > best_u:
                        best_u = cand
                new[u] = best_u
            best[mask] = new

            # Transitions: enter exactly one new town via one edge
            for a, b, w in edges:
                if (mask >> a) & 1:
                    if ((mask >> b) & 1) == 0:
                        ea = new[a]
                        if ea >= w:
                            nm = mask | (1 << b)
                            ne = ea - w + R[b]
                            if ne > best[nm][b]:
                                best[nm][b] = ne
                elif (mask >> b) & 1:
                    if ((mask >> a) & 1) == 0:
                        eb = new[b]
                        if eb >= w:
                            nm = mask | (1 << a)
                            ne = eb - w + R[a]
                            if ne > best[nm][a]:
                                best[nm][a] = ne

    target = N - 1
    ans = -1
    for mask in range(1 << N):
        if (mask & start_mask) and ((mask >> target) & 1):
            val = best[mask][target]
            if val > ans:
                ans = val

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。