Acwing：香甜的黄油（最短路 两种解法 Python）

解法 Python）"/>

Acwing：香甜的黄油（最短路 两种解法 Python）

题目链接🔗：1127. 香甜的黄油 - AcWing题库

分析：

分析题目大意：归根结底我们要求的就是 在所有牧场中选一个，与所有有奶牛的牧场的距离之和最小。那么我们反向思考，就是以每个牧场作为起点，跑一遍最短路模型，然后计算与有奶牛牧场的距离和即可。

那么问题的关键就是最短路模型了，这里有于没有负权值，用dijkstra或者spfa都可以。虽然都说spfa会被卡数据会退化时间复杂度。但其实就本题而言，堆优化的dijkstra和SLF优化的spfa的运行时间几乎完全一样，甚至spfa略胜一筹，这里给出两种解法的代码。

由于本题几乎是spfa和dijkstra的模版题，spfa和dijkstra实现的原理就不多加赘述了。

SPFA代码（Python3 6181ms）

import collections
N,P,C = map(int,input().split())
INF = 999999
res = INF
start = []
for i in range(N) : start.append(int(input()))
Map = [[INF for i in range(P+1)]for j in range(P+1)]
for i in range(C) :a,b,c = map(int,input().split())Map[a][b] = Map[b][a] = cdef spfa(s) :tot = 0queue = collections.deque() # 双端队列的SFL优化queue.append(s)dis = [INF for i in range(P+1)]dis[s] = 0vis = [0 for i in range(P+1)]vis[s] = 1while queue :now = queue.popleft()vis[now] = 0for i in range(1,P+1) :if Map[now][i] == INF : continueif dis[i] > dis[now] + Map[now][i] :dis[i] = dis[now] + Map[now][i]if not vis[i] :vis[i] = 1# SFL优化 如果当前点的dis小于队头元素的dis，则插入队头，反之队尾if len(queue) != 0 and dis[i] < dis[queue[0]] : queue.appendleft(i)            else : queue.append(i)for item in start :if dis[item] > INF//2 : return INF # 如果这点不可达，直接返回无穷大tot += dis[item]return totfor i in range(1,P+1) : # 对于每个点跑一遍最小路res = min(res,spfa(i))
print(res)

Dijkstra代码（Python3 6287ms）

import heapqINF = 999999
res = INF
N,P,C = map(int,input().split())
start = []
for i in range(N) : start.append(int(input()))
Map = [dict() for i in range(P+1)] # 字典存图
for i in range(C) :a,b,c = map(int,input().split())Map[a][b] = Map[b][a] = cdef dijkstra(s) :tot = 0vis = [0 for i in range(P+1)]dis = [INF for i in range(P+1)]dis[s] = 0queue = []heapq.heappush(queue,[dis[s],s]) # 堆优化while len(queue) > 0 :ds,node = heapq.heappop(queue)if vis[node] : continue # 如果这个点已经被扩展过了vis[node] = 1for item in Map[node].keys() :new_dis = dis[node] + Map[node][item]# dis可以被更新且这个点还没有被扩展过if dis[item] > new_dis and not vis[item] : dis[item] = new_disheapq.heappush(queue,[dis[item],item])for i in start :if dis[i] > INF // 2 : return INF # 同SFFAtot += dis[i]return totfor i in range(1,P+1) :res = min(res,dijkstra(i))
print(res)