引入
求非负权边的单源最短路
时间复杂度 O( m l o g n mlogn mlogn)
模板
https://www.luogu.com.cn/problem/P4779
import heapq as hq def dijkstra(s): # dis表示从s到i的最短路 dis = [float('inf')] * (n + 1) # vis表示i是否出队列 vis = [0] * (n + 1) q = [] dis[s] = 0 hq.heappush(q, (0, s)) while q: d, u = hq.heappop(q) if vis[u]: continue vis[u] = 1 for v, w in g[u]: dis[v] = min(dis[v], dis[u] + w) hq.heappush(q, (dis[v], v)) for i in range(1, n + 1): if dis[i] == float('inf'): dis[i] = -1 return dis[1:] n, m, s= map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(m): u, v, w = map(int, input().split()) g[u].append((v, w))
print(*dijkstra(s))
实战演练
L2 001 紧急救援
维护多个数组并得到具体路径
import heapq as hq
import sys
input = sys.stdin.readline
inf = float('inf') def dijkstra(s, ed): q = [] vis = [0] * n dis = [inf] * n pre = [-1] * n cnt = [0] * n # 最短路径数量 res = [0] * n # 能召集的最大救援队数量 dis[s] = 0 cnt[s] = 1 res[s] = a[s] hq.heappush(q, (0, s)) while q: d, u = hq.heappop(q) if u == ed: return dis[ed], cnt[ed], res[ed], pre if vis[u]: continue vis[u] = 1 for (v, w) in g[u]: if dis[v] > dis[u] + w: dis[v] = dis[u] + w cnt[v] = cnt[u] res[v] = res[u] + a[v] pre[v] = u hq.heappush(q, (dis[v], v)) elif dis[v] == dis[u] + w: cnt[v] += cnt[u] # 更新最短路径数量 if res[v] < res[u] + a[v]: res[v] = res[u] + a[v] pre[v] = u return -1, -1, -1, pre n, m, s, ed = map(int, input().split())
a = list(map(int, input().split()))
g = [[] for _ in range(n)]
for _ in range(m): u, v, w = map(int, input().split()) g[u].append((v, w)) g[v].append((u, w)) # 无向图 dist, cnt, res, pre = dijkstra(s, ed)
if dist != -1: print(cnt, res) path = [] while ed != -1: # 从终点回溯路径 path.append(ed) ed = pre[ed] path.reverse() # 反转路径 print(' '.join(map(str, path)))
https://www.lanqiao.cn/problems/3818/learning/
import sys
import heapq as hq
input = sys.stdin.readline def get(c): if c == '.': return 0 else: return ord(c) - ord('A') + 1 def dijkstra(): q = [] dis = [[float('inf')] * m for _ in range(n)] vis = [[0] * m for _ in range(n)] dis[x1][y1] = 0 hq.heappush(q, (0, x1, y1)) while q: d, x, y = hq.heappop(q) if x == x2 and y == y2: return d if vis[x][y]: continue vis[x][y] = 1 for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]: nx, ny = x + dx, y + dy if 0 <= nx < n and 0 <= ny < m and a[nx][ny] != '#' and not vis[nx][ny]: dis[nx][ny] = min(dis[nx][ny], dis[x][y] + get(a[nx][ny])) hq.heappush(q, (dis[nx][ny], nx, ny)) return float('inf') n, m = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1 -= 1
x2 -= 1
y1 -= 1
y2 -= 1
a = [input() for _ in range(n)]
e = int(input()) if e >= dijkstra(): print('Yes')
else: print('No')
https://ac.nowcoder.com/acm/contest/99909/E
对于每条边 ( u , v ) (u,v) (u,v)，如果这条边在某条最短路上的话，则一定满足:
dis[u] + w + dis[v] == dis[n] ,即 最短路从 1 到 u ，再从 u 到 v ，再从 v 到 n 最短路从 1 到 u，再从 u 到 v，再从 v 到 n 最短路从1到u，再从u到v，再从v到n。(或者是 u , v u,v u,v反过来)
import sys
input = sys.stdin.readline
inf = float('inf')
import heapq as hp def dijkstra(s): dis = [inf] * (n + 1) vis = [0] * (n + 1) q = [(0, s)] dis[s] = 0 while q: d, u = hp.heappop(q) if vis[u]: continue vis[u] = 1 for v, w in g[u]: if dis[v] > dis[u] + w: dis[v] = dis[u] + w hp.heappush(q, (dis[v], v)) return dis t = int(input())
for _ in range(t): n, m = map(int, input().split()) g = [[] for _ in range(n + 1)] edge = [] for i in range(m): u, v, w = map(int, input().split()) g[u].append((v, w)) g[v].append((u, w)) edge.append((u, v, w)) dis1 = dijkstra(1) disn = dijkstra(n) res = [] for u, v, w in edge: # 检查是否在最短路径中 if dis1[u] != inf and disn[v] != inf and (dis1[u] + w + disn[v] == dis1[n]): res.append('1') elif dis1[v] != inf and disn[u] != inf and (dis1[v] + w + disn[u] == dis1[n]): res.append('1') else: res.append('0') print(''.join(res))
END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢