Overview

To maximize the “profit” — the total satisfaction (score) from visiting tourist spots minus the travel cost (transportation expenses) — we use bit DP (subset DP) to exhaustively search over “which set of spots to visit and in what order to visit them.”

Analysis

• The profit is
  $\( (\text{total satisfaction of visited spots}) - (\text{total transportation cost of traveled roads}) \)$ Satisfaction depends only on “whether a spot was visited or not” — even if you pass through the same place multiple times, the satisfaction is counted only once.
• On the other hand, there are infinitely many ways to travel (routes), so naively enumerating all possible “walks (routes)” is impossible.
  For example, even considering only “the order of visits,” with \(N=12\) there are up to \(12! \approx 4.8\times 10^8\) possibilities, which would cause TLE.
• Key observations:
  • Once you decide “the set of spots to visit” and “the order of visitation,” the optimal strategy for each segment is to take the shortest path (there is no reason to take a detour).
  • Therefore, instead of dealing with movement on the original graph directly, we precompute the all-pairs shortest distances \(dist[a][b]\) and treat it as if “any two points can be reached at minimum cost.”
• Furthermore, in this problem, all satisfaction values \(P_i\) are positive.
  Because of this, if you pass through another spot during travel (= visit it), the satisfaction automatically increases, so you can include that spot in the “visited set.” Ultimately, it suffices to exhaustively search over which set to consider as visited and take the maximum.

Algorithm

There are three main stages.

1. All-Pairs Shortest Distances (Floyd–Warshall)

First, compute the minimum transportation cost \(dist[i][j]\) between any two spots.

• Initialization: use the edge cost where an edge exists, \(\infty\) where it doesn’t, and \(dist[i][i]=0\)
• Update:
  $\( dist[i][j] = \min(dist[i][j],\ dist[i][k] + dist[k][j]) \)$ This allows us to treat “movement costs between spots” as if on a complete graph.

2. Precompute the Total Satisfaction for Each Subset

Represent subsets as bitmasks (\(0 \sim 2^N-1\)).

• \(sumP[mask]\): total satisfaction of vertices included in mask
  This can be efficiently precomputed using the standard technique of extracting the lowest set bit.

3. Bit DP to Find the “Minimum Cost to Visit Each Subset”

DP definition:

• \(dp[mask][v]\):
  The minimum travel cost when starting from \(S\), having visited the set of spots represented by mask, and currently being at vertex \(v\)

Initial value: - \(dp[1\ll S][S] = 0\)

Transition: - Visit a not-yet-visited vertex \(u\) next: $\( dp[mask \cup (1\ll u)][u] = \min\left(dp[mask \cup (1\ll u)][u],\ dp[mask][v] + dist[v][u]\right) \)$

Finally, for every mask that contains both \(S\) and \(T\): - The minimum cost for that mask is \(dp[mask][T]\) - The profit is \(sumP[mask] - dp[mask][T]\) So, the answer is the maximum of these values.

Complexity

• Time complexity:
  
  • Floyd–Warshall: \(O(N^3)\)
    
  • Bit DP: \(O(2^N \cdot N^2)\)
    Total: \(O(N^3 + 2^N N^2)\)
• Space complexity:
  
  • \(dist\): \(O(N^2)\)
    
  • \(dp\): \(O(2^N \cdot N)\)
    Total: \(O(2^N N + N^2)\)

(Since \(N\le 12\), we have \(2^N N^2 \approx 4096 \times 144\), which is fast enough.)

Implementation Notes

• Use 0-indexing throughout: Subtract 1 from the input values \(S,T,U,V\) to simplify implementation.

• Set INF to a large value: Use something like 10**18 that won’t overflow when added.

• Since dp represents “minimum cost,” initialize with INF and update using min.

• Since the answer is the “maximum profit,” scan all masks at the end and take max(sumP[mask] - dp[mask][T]) (only for masks that contain both \(S\) and \(T\) and are reachable).

  Source Code

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

---

This editorial was generated by gpt-5.2-high.