在做题时有时候会遇到需要图论建模后跑类似最短路思想的算法,但是该如何区分使用 SPFA 还是 Dijkstra?
例如 旅游巴士 一题中在从堆中取出一个 disudis_udisu 之后,如果不满足 dis>=wdis>=wdis>=w 的 disdisdis 执行 dis+=⌈w−disk⌉×kdis+= \lceil \frac{w-dis}{k} \rceil \times kdis+=⌈kw−dis⌉×k 操作,如何判断此时 Dijkstra 是否可行,即一个点在更新过其他点的最短路后自身的最短路是否会被其他点再次更新?