概要

観光スポットを訪れた満足度の合計から移動コストを引いた利得を最大化する経路を求める問題です。同じスポットを複数回訪れても満足度は1回しか加算されません。

考察

各観光スポットの訪問状態を管理する必要があります。同じスポットを複数回訪れても満足度は1回しか加算されないため、どのスポットを訪れたかを記録しながら探索する必要があります。Nが最大12と小さいため、ビットマスクを用いて訪問状態を表現できます。各状態（どのスポットを訪れたか）と現在位置の組み合わせに対して利得の最大値を記録しながら探索します。

アルゴリズム

ビットマスクを用いた状態空間探索（BFS）を採用します。状態を（訪問済みスポットのビットマスク, 現在位置）の組で表し、各状態における利得の最大値をDPテーブルに記録します。各状態からは隣接するスポットへ移動し、移動先が未訪問の場合は満足度を加算し、訪問済みの場合は交通費のみを引きます。ゴールTに到達した時点での利得の最大値が答えとなります。

計算量

• 時間計算量: \(O(2^N \times N \times M)\)
• 空間計算量: \(O(2^N \times N)\)

実装のポイント

• 状態数を\(2^N \times N\)で管理するDPテーブルを初期化

• 初期状態（スタートSのみ訪問済み）からBFSで探索

• 各移動で、訪問済みかどうかで満足度の加算有無を切り替え

• より高い利得が見つかった状態のみキューに追加

• ゴールTに到達するたびに答えを更新

  ソースコード

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

この解説は deepseekv3 によって生成されました。