Overview

This is a problem on a graph consisting of towns and roads, where visiting each town for the first time restores stamina. We need to find the maximum stamina upon arrival when traveling from town 1 to town N.

Analysis

The key point of this problem is the constraint that even if you visit the same town multiple times, stamina recovery only occurs on the first visit. This means which towns have been visited (whether recovery has already occurred) is important as part of the state. Additionally, since stamina can grow arbitrarily large through recovery, a simple Dijkstra’s algorithm cannot handle this well (there are no negative edges, but there is no upper bound).

By combining two components as the state — “the current town” and “the set of towns visited so far (the set of towns where recovery has been used)” — we can solve the problem efficiently. By recording and updating the maximum stamina at each state, we can find the optimal solution.

Algorithm

We use bit DP (dynamic programming). The state is represented as \((used, v)\): - \(used\): A bitmask representing the set of towns visited so far (where recovery has been used) (\(N\) bits) - \(v\): The current town (0-indexed)

For each state \((used, v)\), we record the maximum stamina upon reaching that state in \(dp[used][v]\).

The initial state is \((1<<0, 0)\), with initial stamina \(F + R_0\). Then, we update states as follows: 1. From the current state \((used, v)\), for each road \((u, w)\) connected to \(v\) 2. Movement is possible if the current stamina is at least \(w\) 3. Stamina after moving is \(dp[used][v] - w\) 4. If the destination \(u\) has not been visited (not included in \(used\)), add recovery \(R_u\) 5. Update if the stamina at the new state \((new\_used, u)\) is greater than the previously recorded value

Repeat this until no more updates occur, and the final answer is the maximum stamina across all states \((used, N-1)\).

Complexity

• Time complexity: \(O(2^N \cdot N \cdot M)\)
• Space complexity: \(O(2^N \cdot N)\)

Since \(N \leq 10\), there are \(2^{10} = 1024\) states, which is a sufficiently practical computation size.

Implementation Details

• The number of states is \(2^N \times N\), and each state is initialized with a sufficiently small value (\(-10^{18}\))

• The stamina of the initial state \((1<<0, 0)\) is set to \(F + R[0]\)

• Loop until no more updates occur (an update method similar to the Bellman-Ford algorithm)

• Since each road allows bidirectional movement, build an adjacency list as an undirected graph

• Finally, check the maximum stamina at town \(N-1\) across all states

  Source Code

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

This editorial was generated by deepseekv3.