代码随想录冲冲冲 Day60 图论Part11
97. 小明逛公园
floyd算法 其实就是先用i和j拼成一个平面 然后看每次从i到j距离
这里分两种情况
1.中间没有经过别的点
2.中间有经过别的点
那么最小步数就要取这两个的最小值
所有根本逻辑是i j确定一个面 再通过不同的k去看每一个中间点
所以k要在最外层 上一次的值要作用在下一次当中
卡码网KamaCoder
127. 骑士的攻击
Astar算法 根本来说就是一个bfs的加强版
通过定义一个计算的距离 从而一步一步的去迭代
priority_queue就是用来排序的
对于每一个点来说 要根据
// F = G + H
// G = 从起点到该节点路径消耗
// H = 该节点到终点的预估消耗
来计算
这里的函数公式有几种 可以选择欧拉距离
之后进行bfs 在到一个新的一个的时候 更新全部的参数 并根据计算的f排列放入que中
这个放入que中的点就是距离终点最近的点
直到到终点为止
卡码网KamaCoder