这道题是否为错题？

P1983 [NOIP2013 普及组] 车站分级

lml0928 @ 2024-07-02 15:34:02

题目时间复杂度是立方级别的，最大情况下会达到 1000^3=10^9 的量级，这个在一秒钟内感觉还是不太够啊。

by lml0928 @ 2024-07-02 15:35:04

而且看到 1000 的数据范围会自然的想到是 n^2 或 n^2 \log n 的复杂度。

by 迟暮天复明 @ 2024-07-02 15:45:37

看了一眼，我的写法是平方的

by Miss_SGT @ 2024-07-02 15:46:44

其实可以用一种建图方式做到 O(nm)

设置一下边权就行了

by Miss_SGT @ 2024-07-02 15:47:11

字错了，是终点

by Hanrui1206 @ 2024-07-02 15:47:42

66ms

by Argvchs @ 2024-07-02 17:21:08

@lml0928 1s 1e9 很正常吧

by lml0928 @ 2024-07-02 17:49:23

@Argvchs @Miss_SGT thx.

此帖已结

|