概要

各観光スポットの満足度（得点）を集めつつ、移動コスト（交通費）を差し引いた「利得」を最大化するために、「どのスポット集合を訪れ、どんな順に回るか」を bit DP（部分集合 DP）で全探索します。

考察

• 利得は
  $\( (\text{訪れたスポットの満足度の合計}) - (\text{通った道路の交通費合計}) \)$ です。満足度は「訪れたかどうか」だけが重要で、同じ場所を何回通っても加算は 1 回分です。
• 一方で道路の通り方（経路）は無限にあり、素朴に「歩き方（経路）」を全探索するのは不可能です。
  例えば「どの順に訪れるか」だけを考えても \(N=12\) で最大 \(12! \approx 4.8\times 10^8\) 通りになり、TLE します。
• 重要な観察：
  • 「訪れるスポットの集合」と「その訪問順」を決めれば、各区間の移動は最短経路を通るのが最適です（余計に遠回りする理由がない）。
  • そこで、元のグラフ上の移動を直接扱うのではなく、全点対最短距離 \(dist[a][b]\) を前計算して「どの 2 点間も最短コストで移動できる」ものとして扱います。
• さらに、この問題では「すべての満足度 \(P_i\) が正」です。
  そのため、もし移動中に別のスポットを通るなら（＝訪れるなら）満足度は自動的に増えるので、そのスポットも「訪問集合」に入れて考えてよく、最終的に どの集合を訪れたことにするか を全探索して最大を取ればよい、という形に落とし込めます。

アルゴリズム

大きく 3 段階です。

1. 全点対最短距離（Floyd–Warshall）

まず、任意の 2 スポット間の最短交通費 \(dist[i][j]\) を求めます。

• 初期化：辺があるところはそのコスト、ないところは \(\infty\)、\(dist[i][i]=0\)
• 更新：
  $\( dist[i][j] = \min(dist[i][j],\ dist[i][k] + dist[k][j]) \)$ これで「スポット間の移動コスト」を完全グラフのように扱えるようになります。

2. 各部分集合の満足度合計を前計算

部分集合を bitmask（\(0 \sim 2^N-1\)）で表します。

• \(sumP[mask]\)：mask に含まれる頂点の満足度合計
  これは下位 1bit を取り出す典型テクで高速に前計算します。

3. bit DP で「その集合を訪れる最小コスト」を求める

DP の定義：

• \(dp[mask][v]\)：
  スタート \(S\) から出発し、集合 mask のスポットを訪問済みで、現在地が \(v\) のときの最小移動コスト

初期値： - \(dp[1\ll S][S] = 0\)

遷移： - まだ訪れていない \(u\) を次に訪れる： $\( dp[mask \cup (1\ll u)][u] = \min\left(dp[mask \cup (1\ll u)][u],\ dp[mask][v] + dist[v][u]\right) \)$

最後に、\(S\) と \(T\) を含むあらゆる mask について、 - そのときの最小コストは \(dp[mask][T]\) - 利得は \(sumP[mask] - dp[mask][T]\) なので、これの最大値を答えにします。

計算量

• 時間計算量:
  
  • Floyd–Warshall: \(O(N^3)\)
    
  • bit DP: \(O(2^N \cdot N^2)\)
    合計で \(O(N^3 + 2^N N^2)\)
• 空間計算量:
  
  • \(dist\): \(O(N^2)\)
    
  • \(dp\): \(O(2^N \cdot N)\)
    合計で \(O(2^N N + N^2)\)

（\(N\le 12\) なので、\(2^N N^2 \approx 4096 \times 144\) 程度で十分高速です。）

実装のポイント

• 0-index に統一：入力の \(S,T,U,V\) を -1 して扱うと実装が楽です。

• INF を大きく：10**18 など、足しても溢れない値にします。

• dp は「最小コスト」なので初期値は INF、更新は min。

• 答えは「最大利得」なので、最後に全 mask を走査して max(sumP[mask] - dp[mask][T]) を取ります（ただし \(S,T\) を含み、到達可能なものだけ）。

  ソースコード

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    N = int(next(it))
    M = int(next(it))
    P = [int(next(it)) for _ in range(N)]
    S = int(next(it)) - 1
    T = int(next(it)) - 1

    INF = 10**18
    dist = [[INF] * N for _ in range(N)]
    for i in range(N):
        dist[i][i] = 0

    for _ in range(M):
        u = int(next(it)) - 1
        v = int(next(it)) - 1
        w = int(next(it))
        if w < dist[u][v]:
            dist[u][v] = dist[v][u] = w

    # Floyd-Warshall
    for k in range(N):
        dk = dist[k]
        for i in range(N):
            dik = dist[i][k]
            if dik == INF:
                continue
            di = dist[i]
            base = dik
            for j in range(N):
                nd = base + dk[j]
                if nd < di[j]:
                    di[j] = nd

    ALL = 1 << N

    sumP = [0] * ALL
    for mask in range(1, ALL):
        b = mask & -mask
        i = b.bit_length() - 1
        sumP[mask] = sumP[mask ^ b] + P[i]

    dp = [[INF] * N for _ in range(ALL)]
    dp[1 << S][S] = 0

    for mask in range(ALL):
        dpm = dp[mask]
        for v in range(N):
            cur = dpm[v]
            if cur == INF:
                continue
            dv = dist[v]
            for u in range(N):
                if mask >> u & 1:
                    continue
                du = dv[u]
                if du == INF:
                    continue
                nmask = mask | (1 << u)
                nd = cur + du
                if nd < dp[nmask][u]:
                    dp[nmask][u] = nd

    ans = -INF
    for mask in range(ALL):
        if ((mask >> S) & 1) == 0 or ((mask >> T) & 1) == 0:
            continue
        cost = dp[mask][T]
        if cost == INF:
            continue
        profit = sumP[mask] - cost
        if profit > ans:
            ans = profit

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。