注意:此题理论上正解不是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掉的建议写一下缩点。这确实是一道缩点+拓扑排序的好题,具有思维难度。