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 们给我建议,感激不尽。
另外,感觉这样很容易误导新手去写错误的严格次短路,还是建议撤下错误题解。