概要

\(N\) 個の観光スポットからなるグラフ上で、スタート \(S\) からゴール \(T\) まで移動する際に、「訪問した観光スポットの満足度の合計 − 通過した道路の交通費の合計」を最大化する問題です。同じスポットを複数回通っても満足度は1回分のみ加算されるのがポイントです。

考察

問題の難しさ

この問題が単純な最短路問題と異なるのは、以下の2点です。

1. 同じスポットの満足度は1回しかカウントされない → 「どのスポットを訪問済みか」を管理する必要がある
2. 同じスポットを複数回通ることが許される → 経路が単純パスとは限らず、遠回りしてでも満足度の高いスポットを経由した方が得になる場合がある

例えば、\(S \to A \to B \to A \to T\) のように、一度 \(B\) に寄って戻ってくる経路も考える必要があります。\(B\) の満足度が高ければ、交通費を余分に払っても利得が増える可能性があるからです。

素朴なアプローチの問題点

全ての経路を列挙すると、同じノードを何度も訪問できるため経路数が爆発します。しかし \(N \leq 12\) という制約に注目すると、「訪問済みスポットの集合」をビットマスクで表現できます（\(2^{12} = 4096\) 通り）。

重要な気づき

状態を (現在いるノード, 訪問済みスポットの集合) で表すと、同じ状態に2度以上到達する場合はコストが小さい方だけ残せばよいです。これにより、問題は拡張されたグラフ上での最短路問題に帰着できます。

具体的には、利得 = 満足度合計 − 交通費合計 を最大化する代わりに、交通費合計 − 満足度合計 を最小化する問題に変換します。辺のコストは正（\(W_j \geq 1\)）であり、新しいノードを訪問するときに \(P_v\) を引く（=満足度を得る）操作を行います。辺の重みが非負なので、ダイクストラ法が適用可能です。

アルゴリズム

1. 状態の定義: \((u, \text{mask})\) で「現在ノード \(u\) にいて、これまでに訪問したスポットの集合が \(\text{mask}\)」を表す
2. コストの定義: \(\text{dist}[\text{mask}][u]\) = その状態に至るまでの「交通費合計 − 満足度合計」の最小値
3. 初期状態: \(\text{dist}[1 \ll S][S] = -P_S\)（スタート地点の満足度を得る）
4. 遷移: ノード \(u\) から辺 \((u, v, w)\) を通るとき
   • \(v\) が未訪問なら：新コスト \(= d + w - P_v\)、新マスク \(= \text{mask} \mid (1 \ll v)\)
   • \(v\) が訪問済みなら：新コスト \(= d + w\)、新マスク \(= \text{mask}\)（満足度の追加なし）
5. 答え: \(S\) と \(T\) を含む全てのマスク \(\text{mask}\) について \(\text{dist}[\text{mask}][T]\) の最小値を求め、その符号を反転する

ダイクストラ法で遷移のコスト \(w\)（辺の重み）は正ですが、新ノード訪問時に \(-P_v\) が加わるため実効コストが負になりえます。しかし、同じノードを初めて訪問するときにのみ負のコストが発生し、各ノードは高々1回しか初訪問されないため、ダイクストラ法は正しく動作します（マスクが単調に増加する方向の遷移で負コストが生じ、同じ状態への再訪問では常に非負コスト）。

計算量

• 時間計算量: \(O(2^N \cdot N \cdot (N + M) \cdot \log(2^N \cdot N))\)
  • 状態数は \(2^N \times N\)、各状態から隣接辺を探索し、優先度付きキューの操作に \(\log\) がかかる
  • \(N \leq 12\) なので \(2^{12} \times 12 = 49152\) 状態程度であり、十分高速
• 空間計算量: \(O(2^N \cdot N)\)（距離テーブルの分）

実装のポイント

• ビットマスクの扱い: ノード \(i\) の訪問状態は mask & (1 << i) で確認し、mask | (1 << i) で訪問済みに更新する

• 最小化への変換: 「満足度 − コスト」の最大化を「コスト − 満足度」の最小化に変換することで、ダイクストラ法を自然に適用できる

• 答えの復元: 最終的に \(\text{dist}[\text{mask}][T]\) の最小値の符号を反転して出力する。ゴール地点 \(T\) に到達していれば、途中でどのスポットを経由していても構わないため、\(S\) と \(T\) のビットが立っている全マスクを探索する

• 0-indexed への変換: 入力は1-indexedだが、ビットマスク管理のために内部では0-indexedに変換している

  ソースコード

import sys
from heapq import heappush, heappop

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    P = [0] * N
    for i in range(N):
        P[i] = int(input_data[idx]); idx += 1
    
    S = int(input_data[idx]) - 1; idx += 1
    T = int(input_data[idx]) - 1; idx += 1
    
    # Adjacency list
    adj = [[] for _ in range(N)]
    for _ in range(M):
        u = int(input_data[idx]) - 1; idx += 1
        v = int(input_data[idx]) - 1; idx += 1
        w = int(input_data[idx]); idx += 1
        adj[u].append((v, w))
        adj[v].append((u, w))
    
    # State: (current_node, visited_set_bitmask)
    # We want to maximize: sum of P[i] for i in visited - sum of edge costs
    # Equivalent to minimizing: sum of edge costs - sum of P[i] for i in visited
    # Use Dijkstra-like approach on (node, bitmask) states
    # cost[node][mask] = minimum (total edge cost - total satisfaction) to reach node with visited set = mask
    
    INF = float('inf')
    # dist[mask][node] = min cost (edge_cost - satisfaction) 
    # We negate satisfaction: when we visit a new node, we subtract P[i]
    
    dist = [[INF] * N for _ in range(1 << N)]
    
    start_mask = 1 << S
    dist[start_mask][S] = -P[S]  # We start at S, gain P[S], no edge cost yet
    
    # Priority queue: (cost, node, mask)
    pq = []
    heappush(pq, (-P[S], S, start_mask))
    
    while pq:
        d, u, mask = heappop(pq)
        
        if d > dist[mask][u]:
            continue
        
        for v, w in adj[u]:
            new_mask = mask | (1 << v)
            # If v was already visited, no new satisfaction
            if mask & (1 << v):
                new_cost = d + w
            else:
                new_cost = d + w - P[v]
            
            if new_cost < dist[new_mask][v]:
                dist[new_mask][v] = new_cost
                heappush(pq, (new_cost, v, new_mask))
    
    # Find minimum cost over all masks that include both S and T, ending at T
    ans = INF
    required = (1 << S) | (1 << T)
    for mask in range(1 << N):
        if (mask & required) == required:
            if dist[mask][T] < ans:
                ans = dist[mask][T]
    
    # The profit is -ans (since we minimized cost - satisfaction)
    print(-ans)

main()

この解説は claude4.6opus-thinking によって生成されました。