点这里查看
讨论 / 征集题解...
binarie 2009-01-14 20:35:00
点我顶贴 收藏 删除
=.=标程最后最一个点在rq上测900ms..

http://www.rqnoj.cn/Status_Show.asp?SID=92579

请各位大牛提供更好的解法..

#1 guoshi3@2008-09-06 20:47:00
回复 删除
从前八个点来看，你的标程确实比我慢一些。但是嘛...那个....呃.....后两个点我还没过。

数据有啥特别的吗？

#2 binarie@2008-09-06 20:53:00
回复 删除
最后两个点，数据规模大了。。
#3 guoshi3@2008-09-06 20:55:00
回复 删除
呼，终于过了。最后一个点344ms。我就是SPFA。

可是，我有点问题，存点数组我开30000存边的300000死活过不了。后来改成点40000，边500000还是不行。一怒之下，改成了点100000，边1000000。最后两个点才算过了。数据是不是有问题？

#4 binarie@2008-09-06 20:55:00
回复 删除
1L大牛可以大概说一下你的思路嘛

SPFA怎么优化的

#5 binarie@2008-09-06 20:58:00
回复 删除
数据貌似没问题

测试结果9: 测试结果错误.错误结果为:12577

正确结果应为:7554

测试结果10: 测试结果错误.错误结果为:12577

正确结果应为:8087

结果都跟第7个点的相同，

看样子是这两次出现运行错误了，没返回正确的信息。。

#6 binarie@2008-09-06 20:59:00
回复 删除
打错了，是第8个点
#7 guoshi3@2008-09-06 21:01:00
回复 删除
别，别，别叫我大牛。就是暑假最后这半个月狂刷了百十来道水题，但是水平不到牛的地步呢……

我用的前向星，不知道和边表哪个快点。之前在poj上做一道题好像前向星快了点（呃，是快了一倍），而且discuss里，大牛说前向星快。从此我就用这个了...其实我也不太清楚具体谁快。

本来我看你数据规模，n是30000，m是150000，比较稀疏，所以决定用spfa，但是没想到你数据规模不是这个。要是不够稀疏的话我想dijkstra+heap应该更快。

lz用的什么？

#8 guoshi3@2008-09-06 21:04:00
回复 删除
那为什么我把数组开大了很多后就过了。>_<
#9 binarie@2008-09-06 21:07:00
回复 删除
没准下标越界了呢..

我用的也是SPFA...但存图用的是边表,估计差在这里吧..

最后两个点：

9: N=20000 M=67771

10:N=30000 M=137412

范围应该没问题的...

#10 binarie@2008-09-06 21:08:00
回复 删除
额。。。

被拽去吃饭了>_<

一会回来额。。

88

查看更多回复
提交回复