Home Sign Up Sign In
yangkeao
V2EX  ›  问与答

最短路及 IDA*算法，还有 I/O 效率问题

  •   
  •   yangkeao · Sep 7, 2014 via Android · 4301 views
    This topic created in 4446 days ago, the information mentioned may be changed or developed.
    信奥在即，给以前没弄清楚的问题收个尾

    首先，spfa和diJIEsitala(我承认我不会写这个单词，就是OPEN CLOSED两个表的那个)哪个效率更高？

    然后为何IDA*会比A*快？

    还有 自己用getchar写函数比scanf要快，为什么？
  • ida
  • spfa
  • scanf
    9 replies  •  2014-09-07 14:25:17 +08:00
    66CCFF
    66CCFF
    Sep 7, 2014❤️1
    1
    一般来说spfa在稀疏图上效率更高，Dij在稠密图上效率更高。搞OI的话……一般用SPFA加些优化是没问题的，有时候数据大就要考虑堆优化Dij了。。

    水平有限，仅供参考。
    yangkeao
    yangkeao
    OP
    Sep 7, 2014 via Android
    2
    @66CCFF 因为poJ上那道第k短路的问题用dij过了，但是spfa就没过。才想到了这个问题。
    66CCFF
    66CCFF
    Sep 7, 2014
    3
    @yangkeao 欢迎到 https://vijos.org/ 做题和参加模拟赛~
    今晚刚刚进行完一场比赛。近期比赛的题目质量都会很高的~
    xjx0524
    xjx0524
    Sep 7, 2014❤️1
    4
    @66CCFF vijos 逝去的青春啊。。。
    66CCFF
    66CCFF
    Sep 7, 2014
    5
    @xjx0524 是呀……不过到现在还是刷不动就是了哈哈哈。
    aheadlead
    aheadlead
    Sep 7, 2014
    6
    Dijkstra
    yangkeao
    yangkeao
    OP
    Sep 7, 2014❤️1
    7
    @66CCFF 我们学校好像有vijos的开发之一哦~~~
    lsylsy2
    lsylsy2
    Sep 7, 2014
    8
    @66CCFF vijos居然活了？
    另外单词是dijkstra吧
    66CCFF
    66CCFF
    Sep 7, 2014
    9
    @lsylsy2 活了有2年了。中间停了3年的样子~
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Privacy   ·   Solana   ·   3994 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 42ms · UTC 07:15 · PVG 15:15 · LAX 23:15 · JFK 02:15
    ♥ Do have faith in what you're doing.