原題:SHPATH 题意很简单,但是因为测试数据非常庞大,非常容易超时。推荐使用Dijkstra+BinaryHeap的算法,不过我的程序是没有通过的,Python写的代码光是读取数据就要用8s,并且即使读取结束,也总会运行时错误。 在tutorial组的题目中有一个Turtle’s Shortest Path TSHPATH,题目完全一样,测试数据也一样,除了时间限制很宽松,可以用来测试程序是否正确。 我后来编写了C版本的Dijkstra+BinaryHeap的代码,却总是WA,而用我自己特地生成的随机数据进行测试结果却完全正确(对比了问牛人要来的代码运行的结果)。 下面是我的代码,如果有牛人路过,希望能指出其中的错误: Python版(我记得有些许小错误,因为某些数据和C版本不一致),C版本 gengraph测试数据生成脚本,不过可能会产生孤点。
关于我
- 曹力
- 程序员 / 架构师
- JavaScript高级程序设计译者
- NirvanaStudio精神领袖
版权声明
本 Blog 所有文章若无特别声明都遵循创作共用约定,要求署名、非商业、保持一致。转载时请先阅读以上许可协议,并以超链接形式注明出处。分类目录
-
RSS Links
Blogroll
Nirvana Studio
其他
标签
功能
-
