2024.7.7刷题记录

目录

一、849. Dijkstra求最短路 I - AcWing题库

二、850. Dijkstra求最短路 II - AcWing题库

---

根据讲解视频写的代码

一、849. Dijkstra求最短路 I - AcWing题库

N = 600
MAXL = 10010    # 最长边长
# 稠密图邻接矩阵
g = [[MAXL] * N for _ in range(N)]
dist = [MAXL] * N   # 储存到节点1的距离
st = [False for _ in range(N)]R = lambda: map(int, input().split())
n, m = R()
for _ in range(m):x, y, z = R()g[x][y] = min(g[x][y], z)   # 重边保留最小值def dijkstra() -> int:dist[1] = 0for _ in range(n):# 寻找未知节点中的最短距离节点t = -1for i in range(1, n + 1):if not st[i] and (t == -1 or dist[t] > dist[i]):t = i# 放入sst[t] = True# 更新节点for i in range(1, n + 1):dist[i] = min(dist[i], dist[t] + g[t][i])return -1 if dist[n] > 10000 else dist[n]print(dijkstra())

二、850. Dijkstra求最短路 II - AcWing题库

# 堆优化版
import heapq
# 稀疏图用邻接表
N = int(2e5)
# 头节点初始化为-1、值为最大值
h = [-1] * N; e = [0] * N; ne = [0] * N; val = [0] * N; idx = 0
st = [False] * N
dist = [float('inf') for _ in range(N)]     # 初始化成无穷大
q = []  # 堆def add(x, y, z):global idxe[idx] = yval[idx] = zne[idx] = h[x]h[x] = idxidx += 1R = lambda: map(int, input().split())
n, m = R()
for _ in range(m):x, y, z = R()add(x, y, z)def dijkstra():dist[1] = 0heapq.heappush(q, (0, 1))while q:# 寻找distance, ver = heapq.heappop(q)if st[ver]: continue# 放入sst[ver] = True# 更新其他节点cur = h[ver]while cur != -1:j = e[cur]if dist[j] > distance + val[cur]:dist[j] = distance + val[cur]heapq.heappush(q, (dist[j], j))     # 更新时，冗余存储cur = ne[cur]return dist[n]
ans = dijkstra()
print(-1 if ans > int(1e9) else ans)

完

感谢你看到这里一起！加油吧！