Overview

This problem involves an adventurer with stamina traversing a graph composed of towns and roads, seeking to maximize the final stamina upon reaching town \(N\) from town \(1\). Each town has an inn that restores stamina only once (on the first visit), and the same road can be traversed any number of times.

Analysis

The key to this problem is maintaining the set of visited towns and the current stamina as the state.

A naive approach using simple BFS or DFS tends to create loops from repeatedly going back and forth between the same towns, causing the number of states to explode. Additionally, since stamina values change, simply tracking “whether a town has been visited or not” may cause us to miss the optimal path.

Therefore, we need to manage which towns have been visited using a bitmask and also record the maximum stamina at each point. This allows us to update only when we can reach the same combination of “visited state” and “current location” with higher stamina.

Specifically, we define the state as (bitmask of visited towns, current location) and record the maximum achievable stamina for that state. It is effective to use a priority queue to explore in order of highest stamina, similar to Dijkstra’s algorithm.

Algorithm

The solution uses Dijkstra’s algorithm (or best-first search) with bitmasks.

Steps:

1. Initial state:

   • At town \(1\).
   • Bitmask of visited towns: 1 << 0 (town 1 is set).
   • Initial stamina: \(F + R_1\).

2. State management:

   • visited[(mask, node)] = hp: the maximum stamina achievable when the visited state is mask and the current location is node.
   • Push the initial state into the priority queue: (-hp, mask, node) (stored with negation to simulate a max-heap).

3. Transitions:

   • Move to adjacent towns reachable from the current town.
   • A transition is only possible if the adventurer has enough stamina for the move.
   • If visiting a new town for the first time, stamina is restored at the inn.
   • For the new state (new_mask, next_node), update and add to the queue only if the stamina is higher than previously recorded.

4. Termination condition:

   • When a state reaches town \(N\), record the maximum stamina at that point.
   • After the search completes, output the maximum stamina recorded for town \(N\). Output -1 if it is unreachable.

Complexity

• Since \(N \leq 10\), the number of possible visited states via bitmask is at most \(2^{10} = 1024\).
• Each node can have up to \(2^N\) states, so the total number of states is \(O(N \cdot 2^N)\).
• From each state, up to \(M\) edges can be traversed, so the number of transitions is \(O(M \cdot N \cdot 2^N)\).
• Priority queue operations cost \(O(\log(\text{number of states})) = O(\log(N \cdot 2^N))\).

Therefore,

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

Implementation Notes

• Town numbers are 1-indexed, so adjust the bitmask indices accordingly (e.g., town \(j\) → bit position \(j - 1\)).

• Even for the same state (combination of mask and node), stamina may differ, so it is necessary to always update with the maximum stamina.

• Inn recovery occurs “only on the first visit,” so this must be checked using the bitmask.

• Similar to Dijkstra’s algorithm, prune cases where we arrive at a state with stamina lower than the recorded visited value to speed up the search.

  Source Code

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

This editorial was generated by qwen3-coder-480b.