Overview

Due to the condition that “recovery at each town only happens on the first visit,” we perform a subset DP where the set of visited towns (i.e., which towns have already provided recovery) is part of the state, and we find the maximum health upon arrival at town \(N\).

Analysis

Key Observations

• Health increases only once per town, on the first visit, so “which towns have been visited for the first time” becomes the essential state.
• Since you can traverse the same town or road any number of times, the path length itself can grow infinitely, but recovery events occur at most \(N\) times.
  Therefore, using a “visited set (bitmask)” reduces this to a finite number of states (\(N \le 10\) makes \(2^N\) practical).

Why Naive Search Is Difficult

• If you try to maximize using only “current town” and “health,” you lack information about which towns have already provided recovery, causing the future to differ and leading to WA.
• If you search with “current town,” “health,” and “recovery set,” the number of states is finite, but health has no upper bound (it can increase via recovery), so it doesn’t fit neatly into a standard shortest/longest path framework.

How to Solve This

• Define the state as “recovery set \(mask\)” and “current position \(v\),” and manage the maximum achievable health for each state via DP.
• However, “moving within already-visited towns (no recovery)” can be done any number of times, so for each \(mask\), we use the minimum travel cost (shortest distance) within the visited subgraph to compute at once “how much health can remain when reaching any town while staying in the same \(mask\).”

Algorithm

State Definition

• \(best[mask][v]\):
  The maximum achievable health when the set of first-visited towns is \(mask\) (= the set of towns where recovery has been received) and the current location is town \(v\).
  \(-1\) if unreachable.

Initial state: - Town 1 is treated as first-visited at departure, so
\(best[1 \ll 0][0] = F + R_1\)

1) Reflecting “Free Movement” Within the Same \(mask\) (No Recovery)

As long as you move using only towns included in \(mask\), no new recovery occurs (since recovery has already been received).

Therefore: - Let \(S\) be the set of vertices included in \(mask\). - Compute the shortest distances \(dist_S[i][j]\) using only vertices in \(S\) as intermediate points.

This is “all-pairs shortest paths on the induced subgraph,” so leveraging \(|S| \le 10\), we run Floyd–Warshall only over \(S\).

Once the shortest distances are obtained, within the same \(mask\): - If you can move from \(s \to u\) at cost \(dist_S[s][u]\), the remaining health is \(best[mask][s] - dist_S[s][u]\).

Thus, the achievable health within the same \(mask\) can be updated in one shot: [ best’[mask][u] = \max_{s \in S} (best[mask][s] - dist_S[s][u]) ] (Due to the triangle inequality of shortest distances, this update does not need to be repeated.)

2) Transition to a New Town (Recovery Occurs)

Next, consider the transition of visiting for the first time a town \(x\) not yet in \(mask\).

For edge \((a, b, w)\): - If \(a \in mask\), \(b \notin mask\), and \(best'[mask][a] \ge w\), then - Moving \(a \to b\) consumes \(w\) health, and upon arrival, \(R_b\) recovery is received, so [ best[mask \cup {b}][b] = \max\left(best[mask \cup {b}][b],\; best’[mask][a] - w + R_b\right) ] The reverse direction is handled similarly.

3) Answer

The answer is the maximum value of \(best[mask][N]\) over all \(mask\) that include town \(N\).
If it is never reachable, the answer is \(-1\).

Complexity

• Time complexity: \(O\!\left(2^N \cdot (N^3 + M)\right)\)
  (For each \(mask\), Floyd–Warshall on the subset is at most \(O(N^3)\), and scanning edges for transitions is \(O(M)\).)
• Space complexity: \(O(2^N \cdot N + N^2)\)

Implementation Notes

• Manage the recovery set with bits (town \(i\) as bit \(i-1\)).

• Movement within the same \(mask\) involves “no recovery,” so once shortest distances are known, the maximum health can be updated in bulk: [ \max_s (E_s - dist[s][u]) ]

• For Floyd–Warshall, it suffices to loop only over vertices included in \(mask\) (since \(N \le 10\), copying and running is fast enough).

• Manage unreachable states with \(-1\) and filter them out during comparisons for easier implementation.

  Source Code

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()

---

This editorial was generated by gpt-5.2-high.