AcWing 920. 最优乘车    原题链接    中等

作者： 作者的头像   cqx ,  2020-10-09 19:51:22 ,  所有人可见 ,  阅读 491

1


代码还是 spfa ，进行如下微小修改才是 bfs

具体 spfa 和 bfs 的微小差别：

https://leetcode-cn.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/solution/spfa-bfsde-yi-chong-kuo-zhan-by-fried-chicken/

注意！！！！

只有边权全部为 1 时才能用 bfs，否则还是老老实实用 spfa 算法吧~~~

if (g[t][i] && dist[i] == 0x3f3f3f3f) // 进行了修改，确保每个点只进队出队一次

1 评论

用户头像
cqx   2020-10-09 20:03         踩      回复

只有边权全部为 1 时才能用 bfs，原因是 bfs 的最短路性质，因为能遇见他的第一眼，一定就是最小值，所以不可能被二次更新，而边权大于 1 就不一定了