楼主说的很对，建图是的确需要N^3的复杂度。但是实际请况是每次读入一条线路，最多覆盖长为N的区间，需建的边数为s*(N-s),至多为N^2/4条，实测最大的一个点只有不到20,000,000条边（算重加的）。
by BJpers2 @ 2018-06-07 20:56:11
多打了一个0,只有两千万
by BJpers2 @ 2018-06-07 20:57:46
啊，脑子抽了，我啥也没说
by BJpers2 @ 2018-06-07 20:58:30
不会。最坏复杂度为
```
(n/2)*(n/2)*m=n*n*m/4=1000*1000*250=5000*5000*10.
```
常数优化后能过 。
by retired_treasure @ 2018-06-17 13:06:21
@[Park](/space/show?uid=37509) 毕竟1000³也大不到哪去，只比5000²大40倍，常数优化可过（那些说空循环过不了的，break和continue你们考虑没）
by retired_treasure @ 2018-06-17 13:08:04
@[treasure](/space/show?uid=65534) n<=1000,O(n^3)的复杂度如何才能常数优化到1s以内,求教
by Park @ 2018-06-17 15:25:03