公式

E - 配達員の巡回 / Delivery Person's Round 解説 by sounansya


まず、各届け先間の経路はその届け先同士の経路の中で最短のものを通るとして良いです。

したがって、グラフの情報として必要なものは頂点 \(1\) と届け先合わせて \(K+1\) 頂点の相互の距離です。これらは各頂点を始点としたダイクストラ法を用いることで全体で \(O(K(N+M)\log N)\) 時間で計算することができます。

相互の距離の情報がわかったあとは、これは典型的な巡回セールスマン問題です。\(d[i][S]\) を「頂点集合 \(S\) が既に到達済みで、現在頂点 \(i\) にいるような移動のコストの最小値」とした bitDP を行い、最後に頂点 \(1\) に戻る分のコストを足し合わせたものの最小値を求めれば良いです。

実装例(Python3)

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