Overview

There are roads between tourist spots, and each spot has an assigned satisfaction value. The problem is to choose a route from start to goal that maximizes the “profit,” defined as the total satisfaction of visited spots minus the total transportation cost of roads traveled.

Analysis

This problem is not a simple shortest path problem. Since the profit changes depending on “which tourist spots have been visited,” it cannot be solved with a standard Dijkstra’s algorithm. Specifically, the key point is that even if you revisit the same tourist spot, the satisfaction is only gained once.

A naive approach would be to consider DFS exploring all paths, but since routes that pass through the same vertex multiple times must also be considered, the number of states explodes. In particular, since the number of tourist spots \(N\) is at most 12, there are \(2^{12} = 4096\) possible visitation patterns (subsets), and we need to search efficiently while taking these into account.

Therefore, by representing the “set of visited tourist spots” as a bitmask and applying Dijkstra’s algorithm with visitation state, we can efficiently find the solution.

Algorithm

In this problem, we need to maintain not just the current vertex position but also the information of “which tourist spots have been visited” as part of the state. This is managed using a bitmask.

Extended Dijkstra’s Algorithm

• State: (current tourist spot, bitmask of visited tourist spots)
• dist[v][mask]: the maximum profit when arriving at spot \(v\) with the set of visited spots being mask
• Initial state: Since we start at starting point \(S\), dist[S][1 << (S-1)] = -P[S] (add the initial satisfaction)
• Update process:
  • When moving to an adjacent tourist spot \(v\):
    • If visiting for the first time, add satisfaction \(P_v\)
    • Subtract transportation cost \(W\)
    • Update the bitmask: new_mask = mask | (1 << (v-1))
    • new_profit = profit + (P[v] if newly visited) - W
    • If a better profit is achievable, update and add to the priority queue

Finally, record the maximum profit upon reaching the goal \(T\) as the answer.

Complexity

• Time complexity: \(O(2^N \cdot (N + M))\)
  • For each tourist spot, there are \(2^N\) bitmask states
  • From each state, check up to \(N\) edges
• Space complexity: \(O(2^N \cdot N)\)
  • The dist array has up to \(N \times 2^N\) elements

Implementation Notes

• Be careful that bitmask indices are handled in 0-indexed fashion (e.g., spot 1 → bit 0)
• Satisfaction is added only upon the first visit, so use the bitmask to determine whether a spot has already been visited
• Dijkstra’s algorithm typically finds the minimum distance, but here we want to find the maximum profit, so we insert negative values into the priority queue to simulate a max-heap

## Source Code

```python
import heapq
from collections import defaultdict

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
    P = [0] * (N+1)
    for i in range(1, N+1):
        P[i] = int(data[idx]); idx += 1
    S = int(data[idx]); idx += 1
    T = int(data[idx]); idx += 1
    
    # グラフ構築
    graph = defaultdict(list)
    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))
    
    # ダイクストラ法の拡張
    # dist[v][mask]: スポットvに到達し、訪問済みスポットの集合がmaskであるときの最大利得
    INF = float('inf')
    dist = defaultdict(lambda: defaultdict(lambda: -INF))
    # (利得, 現在地, 訪問済みビットマスク)
    pq = [(-P[S], S, 1 << (S-1))]
    dist[S][1 << (S-1)] = -P[S]
    
    max_profit = -INF
    
    while pq:
        d_neg, u, mask = heapq.heappop(pq)
        profit = -d_neg
        
        if profit < dist[u][mask]:
            continue
            
        if u == T:
            max_profit = max(max_profit, profit)
            
        for v, cost in graph[u]:
            new_mask = mask | (1 << (v-1))
            # 新たに訪れる場合のみ満足度を加算
            added_satisfaction = P[v] if not (mask & (1 << (v-1))) else 0
            new_profit = profit + added_satisfaction - cost
            
            if new_profit > dist[v][new_mask]:
                dist[v][new_mask] = new_profit
                heapq.heappush(pq, (-new_profit, v, new_mask))
    
    print(max_profit)

if __name__ == "__main__":
    main()

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