题解 | 郊区春游

def floyed(n, mp):
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j])
    return mp


def main():
    # 读取输入
    n, m, r = map(int, input().split())
    rs = [0] + list(map(int, input().split()))  # 下标从1开始

    # 初始化邻接矩阵和dp数组
    INF = 0x3F3F3F3F
    mp = [[INF] * (n + 1) for _ in range(n + 1)]
    dp = [[INF] * (r + 1) for _ in range(1 << r)]

    # 读取边的信息
    for _ in range(m):
        u, v, w = map(int, input().split())
        mp[u][v] = w
        mp[v][u] = w

    # Floyd算法求最短路
    mp = floyed(n, mp)

    # 初始化dp数组起始状态
    for i in range(1, r + 1):
        dp[1 << (i - 1)][i] = 0  # 最开始走的那一个点，是没有花费的

    # 状态压缩dp
    len_state = (1 << r) - 1
    for i in range(1, len_state):  # 枚举状态
        for j in range(1, r + 1):  # 枚举起始位置
            jj = 1 << (j - 1)
            if not (i & jj):  # 起始位置肯定是走过的
                continue
            for k in range(1, r + 1):  # 枚举终止位置
                kk = 1 << (k - 1)
                if i & kk:  # 终止位置一定是一个新位置
                    continue
                dp[i | kk][k] = min(dp[i | kk][k], dp[i][j] + mp[rs[j]][rs[k]])

    # 找出最小值
    ans = INF
    for i in range(1, r + 1):
        ans = min(ans, dp[len_state][i])

    print(ans)


if __name__ == "__main__":
    main()