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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3736 天前的主题，其中的信息可能已经有所发展或是发生改变。

信奥在即，给以前没弄清楚的问题收个尾

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

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

还有自己用getchar写函数比scanf要快，为什么？

9 条回复 • 2014-09-07 14:25:17 +08:00

66CCFF

2014-09-07 00:39:28 +08:00

一般来说spfa在稀疏图上效率更高，Dij在稠密图上效率更高。搞OI的话……一般用SPFA加些优化是没问题的，有时候数据大就要考虑堆优化Dij了。。

水平有限，仅供参考。

yangkeao

2014-09-07 00:42:57 +08:00 via Android

@66CCFF 因为poJ上那道第k短路的问题用dij过了，但是spfa就没过。才想到了这个问题。

66CCFF

2014-09-07 00:46:17 +08:00

@yangkeao 欢迎到 https://vijos.org/ 做题和参加模拟赛~
今晚刚刚进行完一场比赛。近期比赛的题目质量都会很高的~

xjx0524

2014-09-07 00:59:02 +08:00

@66CCFF vijos 逝去的青春啊。。。

66CCFF

2014-09-07 01:09:52 +08:00

@xjx0524 是呀……不过到现在还是刷不动就是了哈哈哈。

aheadlead

2014-09-07 01:12:07 +08:00

Dijkstra

yangkeao

2014-09-07 11:54:12 +08:00

@66CCFF 我们学校好像有vijos的开发之一哦~~~

lsylsy2

2014-09-07 14:21:24 +08:00

@66CCFF vijos居然活了？
另外单词是dijkstra吧

66CCFF

2014-09-07 14:25:17 +08:00

@lsylsy2 活了有2年了。中间停了3年的样子~