福州专业做网站广州百度网站推广
47. 参加科学大会（第六期模拟笔试）
根据昨天的dijkstra进行堆优化
使用的原因是点多但边少 所以直接对于边进行操作
1.对于priority_queue来说
这是最小堆, 小于的话就是最大堆
之后由于是根据边来说的 所以新建一个Edge并且初始化一下
之后由于使用了priority_queue来构造最小堆，在加上传入queue中的都是一个点以及点到原点的距离，根据自定义的判断公式，已经默认排好了最小也就是离得最近的。所以每次只要top后 pop掉就可以了
下面的判断是为了避免1 -> 2 -> 3 ->1这种的成环情况
之后就是去更新值 在更新完之后会把还没有访问到的 cur的邻边放入queue中
卡码网KamaCoder
94. 城市间货物运输 I
bellman_ford算法 使用场景是图中有负权重时可以使用
1.什么是松弛
每条边有起点、终点和边的权值。例如一条边，节点A 到 节点B 权值为value，如图：
minDist[B] 表示 到达B节点 最小权值，minDist[B] 有哪些状态可以推出来？
状态一： minDist[A] + value 可以推出 minDist[B] 状态二： minDist[B]本身就有权值 （可能是其他边链接的节点B 例如节点C，以至于 minDist[B]记录了其他边到minDist[B]的权值）
minDist[B] 应为如何取舍。
本题我们要求最小权值，那么 这两个状态我们就取最小的
if (minDist[B] > minDist[A] + value) minDist[B] = minDist[A] + value也就是说，如果 通过 A 到 B 这条边可以获得更短的到达B节点的路径，即如果 minDist[B] > minDist[A] + value，那么我们就更新 minDist[B] = minDist[A] + value ，这个过程就叫做 “松弛” 。
对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离。
如图有n个节点 就松弛n-1次
然后基于
if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) { minDist[to] = minDist[from] + price; 这个核心公式继续更新
另外一点是如果松弛次数大于了n-1就不会继续更新了