泪目
by 111l @ 2020-08-19 10:12:08
我反着跑就A了
by 111l @ 2020-08-19 10:12:48
欸为啥啊
我也是SPFA开始WA2个
然后反着跑就A了
哪位大佬能帮忙解释下啊$QwQ$
by stansxt @ 2020-08-24 14:03:13
@[stansxt](/user/69263) @[111l](/user/114206)
```un
7 7
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
1 5 14
```
这组数据能够很好的解释。
正着跑 SPFASPFASPFA 时,到点5的时候1->2->3->4->5 的路径是最优的,所以会是记录的这个路径,遍历到终点时,只会将5->6->7的路径更新,从而造成答案的错误。
而反着跑 SPFASPFASPFA,就会避免这个问题。
by Rubyonly @ 2020-10-31 10:59:30
@[Rubyonly](/user/335193) 感谢QAQ
by 111l @ 2020-10-31 19:46:34
@[Rubyonly](/user/335193) 多谢大佬
by stansxt @ 2020-11-03 17:50:56