Overview

This is a problem of finding the route that maximizes the profit, defined as the total satisfaction from visiting tourist spots minus the travel cost. Even if the same spot is visited multiple times, the satisfaction is only counted once.

Analysis

We need to manage the visit state of each tourist spot. Since satisfaction is only counted once even if the same spot is visited multiple times, we need to search while recording which spots have been visited. Since N is at most 12, which is small, we can represent the visit state using a bitmask. We search while recording the maximum profit for each combination of state (which spots have been visited) and current position.

Algorithm

We adopt a state-space search (BFS) using bitmasks. A state is represented as a pair of (bitmask of visited spots, current position), and the maximum profit for each state is recorded in a DP table. From each state, we move to an adjacent spot — if the destination has not been visited, the satisfaction is added; if it has already been visited, only the travel cost is subtracted. The maximum profit upon reaching the goal T is the answer.

Complexity

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

Implementation Details

• Initialize a DP table managing \(2^N \times N\) states

• Search via BFS starting from the initial state (only the start S has been visited)

• For each move, toggle whether to add satisfaction based on whether the spot has already been visited

• Only add states to the queue when a higher profit is found

• Update the answer each time the goal T is reached

  Source Code

def main():
    import sys
    from collections import deque
    
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it)); m = int(next(it))
    P = [0] * (n+1)
    for i in range(1, n+1):
        P[i] = int(next(it))
    
    S = int(next(it)); T = int(next(it))
    
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        u = int(next(it)); v = int(next(it)); w = int(next(it))
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    INF = -10**18
    dp = [[INF] * (n+1) for _ in range(1<<n)]
    
    start_mask = 1 << (S-1)
    dp[start_mask][S] = P[S]
    
    q = deque()
    q.append((start_mask, S))
    
    ans = INF
    while q:
        mask, u = q.popleft()
        if u == T:
            ans = max(ans, dp[mask][u])
            
        for v, w in graph[u]:
            new_mask = mask
            if not (mask & (1 << (v-1))):
                new_mask |= (1 << (v-1))
                new_val = dp[mask][u] + P[v] - w
            else:
                new_val = dp[mask][u] - w
                
            if dp[new_mask][v] < new_val:
                dp[new_mask][v] = new_val
                q.append((new_mask, v))
                
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.