首先题目的意思这个初始点是任意的对不?
最初看到这题的解题思路后我在想是不是应该要枚举所有的起始点可是这样复杂度肯定不行.
然后看到所有解题报告都是这样的只将第一个点首先进入队列, 也就是说相当于第一个点是源点
可是如果第一个点是独立的或者第一个点根本就不在最优解的环中那么这样得到的答案肯定是错误的, (难道数据都是包含第一个点的环?)
比如如下数据
4 4
1 1 10 10
1 2 100
2 1 100
3 4 1
4 3 1
他们的答案都是0.01(1~2的环), 可是明显应该就是10.00(3~4的环) (我错了么?)

我的想法是将所有的点以权值0都进入队列, 然后再进行扩展, 这样的话才能检测所有的环.

请指教 谢谢

• Yes, they're wrong (121) evilin 2009-12-29 21:53:32
• Re:对网上解题报告的疑问. 谢谢 (145) upwinder 2010-03-17 23:43:29
  • 第一个点为初始点 不存在楼主给的数据 (0) allen4053040allen 2010-10-01 22:06:04
• Re:对网上解题报告的疑问. 谢谢 (369) gyarenas 2012-08-17 14:43:34