＜代码随想录＞ 算法训练营-2025.01.10

47. 参加科学大会（第六期模拟笔试）

迪杰斯特拉的堆优化版

#堆优化的逻辑是每次在访问到一个点时
#可以将起点到这个点的距离（其实加入的是一个到达点和一个距离值）加入小顶堆中
#每次从小顶堆中取出一条最小边，则起点到这条边对应到达的点一定是最短的
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))
    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    # 终点

# 运行算法并输出结果
result = dijkstra(n, m, edges, start, end)
print(result)

94. 城市间货物运输 I

Bellman_ford算法
思路：循环n-1次，循环中对每条边进行一次松弛

def main():
    n,m=map(int,input().split())
    edges=[]
    for _ in range(m):
        s,t,v=map(int,input().split())
        edges.append([s,t,v])
    
    minDist=[float("inf")]*(n+1)
    minDist[1]=0
    for _ in range(n-1):
        updated=False
        for s,t,v in edges:
            if minDist[s] != float("inf") and minDist[s] + v < minDist[t]:
                minDist[t]=min(minDist[s]+v,minDist[t])
                updated=True
        #当对所有边都松弛一次后，如果没有距离发生变更，则后续也不会再变更
        if not updated:
            break
               
    
    res=str(minDist[-1]) if minDist[-1]!=float("inf") else 'unconnected'
    print(res)
        
        

if __name__ =="__main__":
    main()

原文地址：https://blog.csdn.net/qq_44849862/article/details/145116490

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！