surfish @ 2024-11-29 11:26:05
我的第一版代码在 subtask #4 TLE，subtask #1 平均 5ms
后来改了存图方式，链式前向星改成邻接表，subtask #1 平均 14ms，但是 subtask #4 平均 1.2s，过了
也就是说，大数据跑的快的代码小数据反而跑得慢？
by CarroT1212 @ 2024-11-29 11:36:55
@surfish vector 作为 STL 会自带一些常数，使得它可能会比正常的数组访问要慢一点。
但是另一个较大地影响到程序效率的地方是内存访问的连续性。vector 邻接表在遍历出边的时候很大的内存跳跃并不多，但链式前向星肯定是在整个数组上反复横跳的。
所以在大数据上邻接表存图可能会比链式前向星快。
另一个例子是 ST 表，如果把
by surfish @ 2024-11-29 12:20:45
@CarroT1212
原来是这样，谢谢大佬