\(d[i][X]\) を「現在観光スポット \(i\) におり、（意図的に）到達したことのある観光スポットの集合が \(X\) であるような移動に対する交通費の最小値」と定義した bitDP を考えます。

この bitDP は「観光スポット \(i\) から \(j\) まで行くのにかかる交通費の最小値」を全ての組 \((i,j)\) に対して事前にワーシャルフロイド法などで求めておくことで簡単に計算することができます。

この \(d\) を求めることができれば、全ての \(\lbrace S\rbrace \in X \subset \lbrace 1,2,\ldots,N\rbrace\) に対する \(\displaystyle \sum_{i \in X} P_i- d[T][X]\) の最大値が答えとなります。答えが負の値になる場合があることに注意してください。

実装例(Python3)

n, m = map(int, input().split())
p = list(map(int, input().split()))
s, t = map(int, input().split())
s, t = s - 1, t - 1
INF = 10**18
c = [[INF] * n for _ in range(n)]
for i in range(n):
    c[i][i] = 0
for i in range(m):
    u, v, w = map(int, input().split())
    u, v = u - 1, v - 1
    c[u][v] = c[v][u] = w
for k in range(n):
    for i in range(n):
        for j in range(n):
            c[i][j] = min(c[i][j], c[i][k] + c[k][j])
nn = 1 << n
d = [[INF] * nn for _ in range(n)]
d[s][1 << s] = 0
ans = -INF
for ss in range(nn):
    for i in range(n):
        for j in range(n):
            tt = ss | (1 << j)
            if ss != tt:
                d[j][tt] = min(d[j][tt], d[i][ss] + c[i][j])
        if i == t:
            res = -d[i][ss]
            for j in range(n):
                if (ss >> j) & 1:
                    res += p[j]
            ans = max(ans, res)
print(ans)