@[C C A](/user/78645) 我这边交只有0分啊
by peterwuyihong @ 2021-07-22 18:30:52
可能是`SPFA`被卡了。。。可以把`queue`换成`stack`试试
by jia_shengyuan @ 2021-07-22 18:45:45
@[C C A](/user/78645) 楼主，不是这道题吧
by 天命之路 @ 2021-07-22 18:50:47
```cpp
if (++cnt[u] > 1000) puts("-1"), exit(0);
```
```cpp
if (++cnt[u] > 3500) puts("-1"), exit(0);
```
卡界卡得不一样，显然一个WA一个AC
如果你用最长路，边权都非负，跑遍dijkstra 稳过
SPFA 可能被卡
换成`stack` 大概率更慢
by 天命之路 @ 2021-07-22 18:53:00
@[天命之路](/user/226435)
边权非负跑最长路不是不能用 dij 吗？
您是不是想说非正啊/yun
by zimujun @ 2021-07-22 19:48:13
哦对，说错了，不能用dij
那个稳过的算法是这样的：
边权都非负的时候，跑最长路
先用tarjan 把环缩掉，可以证明如果有解，环内边权均为0，故这个强连通分量内所有的 $dist$ 值都相同。
然后拓扑排序，在新图上求 $dist$ (令 $dist[0]=0$,其余为 $-inf$ ，常规跑即可)
by 天命之路 @ 2021-07-22 21:36:03