AcWing 1135. 新年好-py
原题链接
简单
作者:
viclao
,
2023-11-10 21:55:20
,
所有人可见
,
阅读 43
# 思路:
# 1.分别从亲戚和自己家出发,跑6次最短路
# 2.dfs求不同访问路径的最小值
n, m = map(int,input().split()) # 点、边数量
a = [1] + list(map(int,input().split()))
from math import inf
from collections import defaultdict
g = defaultdict(list)
for _ in range(m):
x,y,t = map(int,input().split())
g[x].append((y,t))
g[y].append((x,t))
from heapq import heappop,heappush
dist = defaultdict(list) # 存储6个源点出发到其他点的最短路
# dj最短路
def dj(start):
dis = [inf]*(n + 1)
dis[start] = 0
q = [(0,start)]
while q:
d,u = heappop(q)
if dis[u] < d:
continue
for v,c in g[u]:
if d + c < dis[v]:
dis[v] = d + c
heappush(q,(dis[v],v))
return dis
for i in range(6):
dist[a[i]] = dj(a[i])
#print(dist)
# dfs求不同访问路径的最小值
ans = inf
vis = [False]*6
def dfs(i,start):
if i == 5:
return 0
else:
ans = inf
for j in range(1,6):
if not vis[j]:
vis[j] = True
ans = min(ans,dist[a[start]][a[j]] + dfs(i + 1,j))
vis[j] = False
# print(i,start,ans)
return ans
print(dfs(0,0))