【代码随想录算法训练营第六十四天|卡码网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]]:
        continue
    visited[cur[1]] = True
    for 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')