关于SPFA算法vector会TLE而邻接表能AC
查看原帖
关于SPFA算法vector会TLE而邻接表能AC
61602
传奇英雄楼主2020/12/15 21:48

注意:此题理论上正解不是SPFA,会被卡。正解应该是缩点+拓扑排序,时间复杂度O(n)。

此题SPFA正向访问边就会TLE,而反着访问边就不会,这是因为SPFA不稳定。而邻接表默认的是反着访问边(后加入的边先被访问)。所以用vector存边TLE第6个点的可以反着访问边试试。

还有某些大佬直接反着存边,例如:@⚡小林子⚡

inline void add(int u, int v, int w) {G[u].push_back((Edge){v, w}); }

用SPFA算法A掉的建议写一下缩点。这确实是一道缩点+拓扑排序的好题,具有思维难度。

2020/12/15 21:48
加载中...