【代码随想录算法训练营第六十四天|卡码网47.参加科学大会、94.城市间货物运输I】
文章目录
- 47.参加科学大会
- 94.城市间货物运输I
47.参加科学大会
其实和昨天的方法差不多，一个是用邻接列表来表示点之间的连接，一个是用小顶堆的方式来存储边的权值，在找最短边的时候不用再去比较。
import heapq
n, m = map(int, input().split())
grid = [[] for _ in range(n+1)]
for i in range(m):s, t, v = map(int, input().split())grid[s].append([v, t])
start = 1
end = n
visited = [False] * (n+1)
minDist = [float('inf')] * (n+1)
minDist[start] = 0
heap = []
heapq.heappush(heap, [0, start])
while heap:cur = heapq.heappop(heap)if visited[cur[1]]:continuevisited[cur[1]] = Truefor edge in grid[cur[1]]:if not visited[edge[1]] and minDist[cur[1]]+ edge[0] < minDist[edge[1]]:minDist[edge[1]] = minDist[cur[1]] + edge[0]heapq.heappush(heap, [minDist[edge[1]], edge[1]])
if minDist[end] < float('inf'):print(minDist[e nd])
else:print(-1)94.城市间货物运输I
Bellman_ford也好理解，就是每次对所有可以连接到的点（即对所有边）都更新一次距离原点的距离，每更新一次就能推断出距离原点+1结点位置的最近距离，那对于n个结点最多需要n-1次更新退出最近的距离。
n, m = map(int, input().split())
grid = []
for i in range(m):s, t, v = map(int, input().split())grid.append([s, t, v])
start = 1
end = n
minDist = [float('inf')] * (n + 1)
minDist[1] = 0
for i in range(n-1):for edge in grid:if minDist[edge[0]]!=float('inf') and minDist[edge[1]] > minDist[edge[0]] + edge[2]:minDist[edge[1]] = minDist[edge[0]] + edge[2]updated = True
if minDist[end]!=float('inf'):print(minDist[end])
else:print('unconnected')