为什么不会超时？

P1983 [NOIP2013 普及组] 车站分级

retep @ 2022-08-02 13:22:04

题解中用的很多的方法是建图然后拓扑排序，但是建图的过程中每行停靠记录都要枚举每个停靠的点，再枚举其它没停靠的点来连边，这样不会变成 n^3 吗。

更准确的来说最差情况应该是 1000 \times 500 \times 1000 ，十年前的评测机真的有这个实力吗。

by Yu_iscolongSUY @ 2022-08-02 13:30:02

核战术CPUandGPU好吧（dogs

by Paris_Commune @ 2022-08-02 13:33:56

@retep 洛谷上的许多题的某些解法在以前是过不了的，很正常

by retep @ 2022-08-02 13:41:54

@LHC427 那个题解应该是写的自己考场上的思路

by Paris_Commune @ 2022-08-02 13:43:34

@retep 哪个啊

by retep @ 2022-08-02 13:44:08

@LHC427 你按时间排序，最早的那几篇

by Paris_Commune @ 2022-08-02 13:46:58

@retep 最早也是2016年写的，加上洛谷评测机比较快吧

by retep @ 2022-08-02 13:50:21

@LHC427 谔谔所以你的意思是几乎没人知道正解吗