bellman-ford算法的思想 :
若有向图有n个点,m条边 。 扫描所有边,对每条边进行一次松弛(即对a,b为端点 , 权重为w的边,dist[b] = min(dist[a] , dist[a] + w )) 重复此流程(最多重复n次)直到没有更新操作发生
例题1 bellmanford板子
给你一张 n 个顶点 m 条边的有向简单图,顶点编号从 1 到 n,每条边都有一个边权,边权为非负整数。
现在有 k 组询问,每组询问读入两个整数 x,y 请求出从 x 号点到 y 号点的最短路的长度。如果不存在从 x 号点到 y 号点的路径,请输出 -1。
输入格式
第一行三个整数 n,m,k表示图的顶点数、边数和询问次数。
接下来 m
标签:cnt,dist,int,短路,Bellman,ford,edge,边权 From: https://www.cnblogs.com/algoshimo/p/17564583.html