公式
E - 配達員の巡回 / Delivery Person's Round 解説
by
E - 配達員の巡回 / Delivery Person's Round 解説
by
sounansya
まず、各届け先間の経路はその届け先同士の経路の中で最短のものを通るとして良いです。
したがって、グラフの情報として必要なものは頂点 \(1\) と届け先合わせて \(K+1\) 頂点の相互の距離です。これらは各頂点を始点としたダイクストラ法を用いることで全体で \(O(K(N+M)\log N)\) 時間で計算することができます。
相互の距離の情報がわかったあとは、これは典型的な巡回セールスマン問題です。\(d[i][S]\) を「頂点集合 \(S\) が既に到達済みで、現在頂点 \(i\) にいるような移動のコストの最小値」とした bitDP を行い、最後に頂点 \(1\) に戻る分のコストを足し合わせたものの最小値を求めれば良いです。
import sys
import heapq
input = sys.stdin.readline
INF = 10**18
def dijkstra(g, st):
n = len(g)
d = [INF] * n
d[st] = 0
pq = [(0, st)]
while pq:
cost, v = heapq.heappop(pq)
if d[v] < cost:
continue
for to, c in g[v]:
nd = d[v] + c
if nd < d[to]:
d[to] = nd
heapq.heappush(pq, (nd, to))
return d
def salesman(a):
n = len(a)
nn = 1 << n
d = [[INF] * nn for _ in range(n)]
d[0][1] = 0
for xx in range(nn):
for i in range(n):
if d[i][xx] == INF:
continue
dix = d[i][xx]
for j in range(n):
yy = xx | (1 << j)
if xx == yy:
continue
nd = dix + a[i][j]
if nd < d[j][yy]:
d[j][yy] = nd
ans = INF
full = nn - 1
for i in range(n):
ans = min(ans, d[i][full] + a[i][0])
return ans
n, m, k = map(int, input().split())
v = list(map(int, input().split()))
v = [x - 1 for x in v]
k += 1
v.insert(0, 0)
g = [[] for _ in range(n)]
for _ in range(m):
u, vv, c = map(int, input().split())
u -= 1
vv -= 1
g[u].append((vv, c))
g[vv].append((u, c))
dist = [[0] * k for _ in range(k)]
for st in range(k):
dd = dijkstra(g, v[st])
for i in range(k):
dist[st][i] = dd[v[i]]
print(salesman(dist))
