SPOJ#15 The Shortest Path

原題:SHPATH

题意很简单,但是因为测试数据非常庞大,非常容易超时。推荐使用Dijkstra+BinaryHeap的算法,不过我的程序是没有通过的,Python写的代码光是读取数据就要用8s,并且即使读取结束,也总会运行时错误。

在tutorial组的题目中有一个Turtle’s Shortest Path TSHPATH,题目完全一样,测试数据也一样,除了时间限制很宽松,可以用来测试程序是否正确。

我后来编写了C版本的Dijkstra+BinaryHeap的代码,却总是WA,而用我自己特地生成的随机数据进行测试结果却完全正确(对比了问牛人要来的代码运行的结果)。

下面是我的代码,如果有牛人路过,希望能指出其中的错误:

Python版(我记得有些许小错误,因为某些数据和C版本不一致),C版本

gengraph测试数据生成脚本,不过可能会产生孤点。

发表评论

电子邮件地址不会被公开。 必填项已用*标注