数据水还是 ……
查看原帖
数据水还是 ……
128754
方123456楼主2022/8/24 19:39

RT,询问关于几篇题解的正确性。

首先有部分题解用了两个路径来分别记录最短路和次短路,个人认为这样做 Dijkstra 的贪心有可能会失效,所以来问一下是不是正确的。

另外附上两个 hack:

4 6 
1 2 8
2 3 7
1 4 10
2 1 8
2 4 1
1 3 7

out
10
5 5 
1 2 5
 2 3 5 
3 4 4 
4 5 6 
1 5 21
out
21

好像能 hack 掉大部分写挂的 Dijkstra ?

还有一种写法就是强制走一条边,跑两回最短路,个人认为这种方式可能是更正确的?

如果有 Dijkstra 不是按上面写法过的,还请 dalao 们给我建议,感激不尽。

另外,感觉这样很容易误导新手去写错误的严格次短路,还是建议撤下错误题解。

2022/8/24 19:39
加载中...