AcWing 1127. 香甜的黄油
原题链接
简单
SPFA
from collections import deque
def spfa(graph,s):
n = len(graph) - 1
## 起点到各点的距离
dis = [0x3f3f3f3f for i in range(n+1)]
## 记录该点是否在队列中
vis = [False for i in range(n+1)]
## 记录起点到该点走过的边数,用去判断是否存在负权值环
cnt = [0 for i in range(n+1)]
dis[s] = 0
q = deque()
q.append(s)
vis[s] = True
## 核心代码
while q:
## 出队列
cur = q.popleft()
vis[cur] = False
## 与该点连接的点进行松弛操作
for node in graph[cur].keys():
new_dis = dis[cur] + graph[cur][node]
if new_dis < dis[node]:
dis[node] = new_dis
## 记录最短路经过的边数
cnt[node] += 1
## 在不经过负环的情况下,最短路至多经过 n - 1 条边
## 因此如果经过了多于 n 条边,一定说明经过了负环
if cnt[node] >= n:
print('图中存在负权值环')
return
if not vis[node]:
q.append(node)
vis[node] = True
return dis
def createGraph(n,m):
graph = [dict() for i in range(n+1)]
for i in range(m):
a, b, c = map(int, input().split())
graph[a][b] = c
graph[b][a] = c
return graph
if __name__ == '__main__':
cows, n, m = map(int, input().split())
cowsLocations = [int(input()) for i in range(cows)]
graph = createGraph(n,m)
res = 0x3f3f3f3f
for i in range(1,n+1):
## 黄油放在依次放在各个农场找最短路径
dis = spfa(graph,i)
sum = 0
for j in cowsLocations:
sum += dis[j]
res = min(res,sum)
print(res)