概要

観光スポット間に道路があり、各スポットには満足度が設定されている。スタートからゴールまでの経路を選び、訪れたスポットの満足度の合計から道路の交通費の合計を引いた「利得」を最大化する問題。

考察

この問題は単純な最短経路問題ではなく、「訪問済みの観光スポット」によって利得が変化するため、通常のダイクストラ法では解けません。
具体的には、同じ観光スポットに再訪問しても満足度は1回しか得られないという点が重要です。

素朴な方法として、全経路を探索するDFSを考えられますが、同じ頂点を複数回通る経路も考慮しなければならないため、状態数が爆発してしまいます。特に、観光スポット数 \(N\) が最大12なので、訪問パターン（部分集合）が \(2^{12} = 4096\) 通りあり、これを考慮した上で効率的に探索する必要があります。

そこで、「訪問済みの観光スポット集合」をビットマスクで表現し、訪問状態付きのダイクストラ法を適用することで、効率的に解を求めることができます。

アルゴリズム

この問題では、単なる頂点の位置だけでなく、「どの観光スポットを訪問したか」という情報も状態として持つ必要があります。これは、ビットマスクを用いて管理します。

ダイクストラ法の拡張

• 状態: (現在の観光スポット, 訪問済み観光スポットのビットマスク)
• dist[v][mask]: スポット \(v\) に到達し、訪問済みスポットが mask のときの最大利得
• 初期状態: スタート地点 \(S\) にいるので、dist[S][1 << (S-1)] = -P[S] （最初の満足度を加算）
• 更新処理:
  • 隣接する観光スポット \(v\) へ移動するとき：
    • 新たに訪問する場合は、満足度 \(P_v\) を加算
    • 交通費 \(W\) を減算
    • ビットマスクを更新：new_mask = mask | (1 << (v-1))
    • new_profit = profit + (新規訪問ならP[v]) - W
    • より良い利得で到達できる場合、更新して優先度付きキューに追加

最終的には、ゴール \(T\) に到達したときの最大の利得を記録して答えとします。

計算量

• 時間計算量: \(O(2^N \cdot (N + M))\)
  • 各観光スポットにつき、\(2^N\) 個のビットマスク状態を持つ
  • 各状態から最大 \(N\) 本の辺をチェック
• 空間計算量: \(O(2^N \cdot N)\)
  • dist 配列が最大 \(N \times 2^N\) の要素を持つ

実装のポイント

• ビットマスクの添字は0-indexedで扱うことに注意（例: スポット1 → ビット0）
• 満足度は訪問時に初めて加算するので、ビットマスクで既訪問かどうか判定する
• ダイクストラ法では最小距離を求めることが多いが、今回は最大利得を求めるので、優先度付きキューに負の値を入れて最大ヒープをシミュレートしている

## ソースコード

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

この解説は qwen3-coder-480b によって生成されました。