47. 参加科学大会（第六期模拟笔试）
2、堆优化版（该方法没看懂）
邻接矩阵的优点：
- 表达方式简单，易于理解
- 检查任意两个顶点间是否存在边的操作非常快
- 适合稠密图，在边数接近顶点数平方的图中，邻接矩阵是一种空间效率较高的表示方法。
缺点：
- 遇到稀疏图，会导致申请过大的二维数组造成空间浪费 且遍历 边 的时候需要遍历整个n * n矩阵，造成时间浪费
邻接表：
邻接表 使用 数组 + 链表的方式来表示。 邻接表是从边的数量来表示图，有多少边 才会申请对应大小的链表。
邻接表的优点：
- 对于稀疏图的存储，只需要存储边，空间利用率高
- 遍历节点链接情况相对容易
缺点：
- 检查任意两个节点间是否存在边，效率相对低，需要 O(V)时间，V表示某节点链接其他节点的数量。
- 实现相对复杂，不易理解
通过边的角度出发解决，直接把 边（带权值）加入到 小顶堆（利用堆来自动排序），那么每次我们从 堆顶里 取出 边 自然就是 距离源点最近的节点所在的边。
import heapq
class Edge:
def __init__(self, to, val):
self.to = to
self.val = val
def dijkstra(n, m, edges, start, end):
# 初始化邻接矩阵
grid = [[] for _ in range(n+1)]
for p1, p2, val in edges:
grid[p1].append(Edge(p2, val))
# 初始化距离数组和访问数组
minDist = [float('inf')] * (n+1)
visited = [False] * (n+1)
pq = []
heapq.heappush(pq, (0, start))
# 起始点到自身的距离为0
minDist[start] = 0
while pq:
cur_dist, cur_node = heapq.heappop(pq)
if visited[cur_node]:
continue
visited[cur_node] = True
for edge in grid[cur_node]:
if not visited[edge.to] and cur_dist + edge.val < minDist[edge.to]:
minDist[edge.to] = cur_dist + edge.val
heapq.heappush(pq, (minDist[edge.to], edge.to))
return -1 if minDist[end] == float('inf') else minDist[end]
# 输入
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
# 起点
start = 1
# 终点
end = n
res = dijkstra(n, m, edges, start, end)
print(res)
94. 城市间货物运输 I
1、Bellman_ford算法
本题依然是单源最短路问题，求 从 节点1 到节点n 的最小费用。 但本题不同之处在于 边的
权值是有负数了。
Bellman_ford是经典的带负权值的单源最短路问题；dijkstra不适用边存在负数的情况；
Bellman_ford算法的核心思想是 对所有边进行松弛n-1次操作（n为节点数量），从而求得目
标最短路。
Bellman_ford的算法核心操作就是（minDist[B] = min(minDist[A] + value, minDist[B])）
对于n-1的问题，需要对所有边松弛几次才能得到 起点（节点1） 到终点（节点6）的最短距
离呢？节点数量为n，那么起点到终点，最多是 n-1 条边相连。
def main():
n, m = map(int, input().strip().split())
edges = []
for _ in range(m):
src, dest, weight = map(int, input().strip().split())
edges.append([src, dest, weight])
# 初始化最短距离
minDist = [float('inf')] * (n+1)
# 节点1对于节点1的最短距离为0
minDist[1] = 0
# 为什么到n，因为是处理n-1的边
for i in range(1, n):
updated = False
for src, dest, weight in edges:
if minDist[src] != float('inf') and minDist[src] + weight < minDist[dest]:
minDist[dest] = minDist[src] + weight
updated = True
# 如边不在更新，则停止回圈
if not updated:
break
# 返回终点权重，未连接到终点
if minDist[-1] == float('inf'):
return 'unconnected'
return minDist[-1]
if __name__ == '__main__':
print(main())