本题的时间复杂度分析,有些不懂,为什么不会超时
  • 板块P1186 玛丽卡
  • 楼主Ryuichi
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/10/21 21:11
  • 上次更新2023/11/5 10:12:56
查看原帖
本题的时间复杂度分析,有些不懂,为什么不会超时
208478
Ryuichi楼主2020/10/21 21:11

假如最短路径是N个点,图是N*(N-1)/2条边,N个点 用dij跑一次,再对最短路上的每一条边断一下,在跑N-1次最短路,一共跑了NNMlogNM*logN, NMlogNN*M*logN,当N是1000的时候,不是时间复杂度已经炸了吗?

2020/10/21 21:11
加载中...