关于图论的几个疑惑

学术版

g1ove @ 2024-03-27 09:40:19

全负权的图能跑 Dij 吗？

求任意点到 1\to n 点的最短路，是否可以建立超级原点，向每个点连边，求单元最短路解决？

by bmatrix @ 2024-03-27 10:30:06

@g1ove

  1. 有最短路首先不能有负环，全负权就只能是 DAG 了，这个随便跑吧

  2. 事实上根本不用建点，直接一开始把这些点都放进队列里就可以

by FerventTemp0 @ 2024-03-27 10:30:15

全负直接判断有没有环，没环 DAG 跑 dp，有环直接 -INF 就行了。。

by g1ove @ 2024-03-27 10:41:27

@Untitled0 thx qwq.

by g1ove @ 2024-03-27 10:41:47

@FerventTempo thx.qaq

|