这题不是没规定起点和终点吗qwq
by VioletIsMyLove @ 2021-09-21 16:12:51
这不是缩点后拓扑跑DAG？
by Kalium @ 2021-09-21 16:13:58
@[amhxyp](/user/188879)
那spfa？
by lqhsr @ 2021-09-21 16:19:36
spfa是任意起点吗到任意终点吗
by lqhsr @ 2021-09-21 16:21:27
明显不是
by VioletIsMyLove @ 2021-09-21 16:28:50
不是，Floyd可以任意起点终点，但时间复杂度是
$n^3$ 级别的
by novax @ 2021-09-21 16:29:00
@[lqhsr](/user/111197) 但是这题你对于每个点为起点跑一趟SPFA的复杂度是可以的
by VioletIsMyLove @ 2021-09-21 16:30:51
@[amhxyp](/user/188879)
@[novax13](/user/291481)
明白了，感谢二位大佬~
by lqhsr @ 2021-09-21 16:53:00
@[amhxyp](/user/188879)
@[novax13](/user/291481)
大佬们，我刚又有个新的想法：
每次topo都要将没有入度的点丢到队列里
这些点不就是dij的起点吗
by lqhsr @ 2021-09-21 17:58:18