概要

この問題は、スタート地点 \(S\) からゴール地点 \(T\) まで移動する際に、訪れた観光スポットの満足度の合計から、移動にかかった交通費の合計を引いた「利得」を最大化する問題です。観光スポットの数 \(N\) が最大 12 と非常に小さいことが特徴で、訪れるスポットの集合をビット列で管理するビットDP（動的計画法）を用いて解くことができます。

考察

1. 訪れるスポットの集合に着目する

同じ観光スポットを何度訪れても満足度は 1 回しか加算されませんが、交通費は通るたびにかかります。そのため、ある観光スポットの集合 \(X\) を訪れると決めた場合、その集合内のスポットをすべて巡りつつ、移動コストを最小化することが利得の最大化に繋がります。

2. 全点対間最短経路の計算

あるスポット \(u\) から \(v\) へ移動する際、直接結ぶ道路を使うよりも他のスポットを経由したほうが安い場合があります。\(N\) が小さいため、ワーシャル・フロイド法を用いて、あらかじめ全スポット間の最短距離を求めておくことができます。これにより、グラフを「どの 2 点間も最短距離で移動できる完全グラフ」として扱うことが可能になります。

3. ビットDPの適用

「訪れたスポットの集合」と「現在地」を状態として持つことで、巡回セールスマン問題（TSP）に似た動的計画法を適用できます。 - 集合 \(X\) を訪れるための最小コストが分かれば、その集合の満足度合計からコストを引くことで、その集合における最大利得が計算できます。

アルゴリズム

1. 最短経路の計算（ワーシャル・フロイド法）

すべての観光スポットのペア \((i, j)\) について、最短移動コスト dist[i][j] を計算します。

2. ビットDPによる最小コストの算出

以下の DP テーブルを定義します。 - dp[mask][u]：現在までに訪れたスポットの集合が mask（ビット表現）であり、最後にいるスポットが u であるときの交通費の最小合計。

遷移式: 現在地 u から次に訪れるスポット v を選ぶとき： dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], dp[mask][u] + dist[u][v])

初期状態は dp[1 << S][S] = 0 （スタート地点 \(S\) のみ訪問、コスト 0）です。

3. 利得の最大化

各 mask について、その集合に含まれる観光スポットの満足度の総和 sum_P[mask] を計算します。 最終的な答えは、ゴール地点 \(T\) を含んでいるすべての状態における以下の値の最大値です。 - 利得 = sum_P[mask] - dp[mask][T]

計算量

• ワーシャル・フロイド法: \(O(N^3)\)
• ビットDP: \(O(2^N \cdot N^2)\)
• 満足度の事前計算: \(O(2^N)\)
• 全体の計算量: \(O(2^N \cdot N^2)\)

\(N \le 12\) のとき \(2^{12} = 4096\) なので、\(4096 \times 144 \approx 5.9 \times 10^5\) 程度の計算量となり、制限時間内に十分間に合います。

実装のポイント

• 1-indexed から 0-indexed への変換: 入力されるスポット番号 \(1 \dots N\) を、配列のインデックスに合わせて \(0 \dots N-1\) に変換して処理します。

• 満足度の合計計算: sum_P[mask] を計算する際、各ビットを走査する代わりに、mask ^ (lowest_bit) の結果を利用すると効率的に計算できます。

• 到達可能性の考慮: ゴール \(T\) に到達できない経路や、初期状態から遷移できない状態は、十分大きな値 INF で初期化して無視するようにします。

  ソースコード

import sys

def solve():
    # Read all input at once and split into tokens for efficiency
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Parse N (number of sightseeing spots) and M (number of roads)
    N = int(input_data[0])
    M = int(input_data[1])
    
    # Parse satisfaction values P_i for each spot
    P = list(map(int, input_data[2:2+N]))
    
    # Parse start spot S and target spot T (convert 1-indexed to 0-indexed)
    S = int(input_data[2+N]) - 1
    T = int(input_data[3+N]) - 1
    
    # Initialize distance matrix for Floyd-Warshall algorithm
    # dist[i][j] will store the shortest path distance between spots i and j
    INF = 10**18
    dist = [[INF] * N for _ in range(N)]
    for i in range(N):
        dist[i][i] = 0
        
    # Parse each road's information and populate the distance matrix
    idx = 4 + N
    for _ in range(M):
        u = int(input_data[idx]) - 1
        v = int(input_data[idx+1]) - 1
        w = int(input_data[idx+2])
        # If multiple roads exist between the same spots, keep the one with the minimum cost
        if w < dist[u][v]:
            dist[u][v] = w
            dist[v][u] = w
        idx += 3
        
    # Floyd-Warshall algorithm to find all-pairs shortest paths
    for k in range(N):
        dist_k = dist[k]
        for i in range(N):
            dist_i = dist[i]
            dist_ik = dist_i[k]
            if dist_ik == INF:
                continue
            for j in range(N):
                if dist_i[j] > dist_ik + dist_k[j]:
                    dist_i[j] = dist_ik + dist_k[j]
    
    # DP table for the Traveling Salesperson Problem on the metric completion
    # dp[mask][u] = minimum road cost to visit at least the nodes in 'mask' and end at node 'u'
    num_masks = 1 << N
    dp = [[INF] * N for _ in range(num_masks)]
    # Starting point: visit only spot S, cost is 0
    dp[1 << S][S] = 0
    
    # Fill the DP table by iterating through all possible subsets (masks)
    for mask in range(1, num_masks):
        # Only consider subsets that include the starting spot S
        if not (mask & (1 << S)):
            continue
        
        # Precompute spots in the mask and spots not in the mask for inner loop efficiency
        set_bits = []
        not_set_bits = []
        for i in range(N):
            if (mask >> i) & 1:
                set_bits.append(i)
            else:
                not_set_bits.append(i)
        
        d_mask = dp[mask]
        for u in set_bits:
            d_mask_u = d_mask[u]
            if d_mask_u == INF:
                continue
            
            dist_u = dist[u]
            # Transition: move from spot u (in current mask) to spot v (not in mask)
            for v in not_set_bits:
                new_mask = mask | (1 << v)
                new_cost = d_mask_u + dist_u[v]
                if dp[new_mask][v] > new_cost:
                    dp[new_mask][v] = new_cost
    
    # Precompute the sum of satisfaction values for each subset of spots
    sum_P = [0] * num_masks
    for mask in range(1, num_masks):
        # Use the lowest set bit to compute the sum incrementally based on smaller subsets
        lowest_bit = mask & -mask
        bit_index = lowest_bit.bit_length() - 1
        sum_P[mask] = sum_P[mask ^ lowest_bit] + P[bit_index]
        
    # Calculate the maximum profit: (sum of satisfactions) - (total road costs)
    max_profit = -INF
    for mask in range(num_masks):
        # A valid move sequence must end at the target spot T, so T must be in the mask
        if (mask & (1 << T)):
            if dp[mask][T] != INF:
                profit = sum_P[mask] - dp[mask][T]
                if profit > max_profit:
                    max_profit = profit
                    
    # Output the result
    print(max_profit)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。