。。
我用spfa过的。。500多ms。。。
O(VE)是上界吧。。基本达不到。。
下界貌似是O(E)。。

• Re:分明就是dijkstra.....SPFA也是O(VE)吧 (80) frkstyc 2009-01-09 14:11:38
  • 同样的代码复制粘贴，原先的程序跑了1.4s现在跑了2.4s，这又是怎么回事- - (16) wywcgs 2009-01-09 16:16:36
    • 我一直觉得去年写的评测 kernel 比原来更加 robust 的同时效率也更低些吧…… (0) frkstyc 2009-01-09 22:53:34
      • 好些以前可以ac的题现在ac不了，以前设的时限相对现在的评测速度太紧了 (16) LiZhiXu 2009-01-10 19:49:20
        • 这个时间点具体能卡到什么时候…… (20) wywcgs 2009-01-10 20:38:28
          • 具体我也说不清楚，但是我觉得对于大多数题目来说其实时限是更宽了 (23) frkstyc 2009-01-11 14:00:40
• 要我说堆+dijkstra下界也是O(E)…… (188) wywcgs 2009-01-09 16:21:34
  • 怎么wy突然有兴致来翻这个老贴呢？ (79) richardxx 2009-01-09 17:37:43
    • 因为有人比我先翻老贴…… (22) wywcgs 2009-01-09 17:39:25
  • Re:要我说堆+dijkstra下界也是O(E)…… (255) frkstyc 2009-01-09 22:55:53
    • 一说猥琐，我就想起了你那次平面点集最小生成树+平面图最小切割等等的那次比赛…… (22) wywcgs 2009-01-10 20:57:20
      • 那次是清华出的题吧…… (26) lunatec 2009-01-10 21:13:02
        • 我是说pku monthly的题……　清华的那道平面图最小切割比styc当初出的那道好写百倍…… (0) wywcgs 2009-01-10 21:18:16
          • 你是说拓扑变换啊，那的确是。。。 (0) lunatec 2009-01-10 21:27:24
          • 不就是少了 2KB 的代码…… (0) frkstyc 2009-01-11 14:02:13