直接翻译了
Descriptions
Bessie搬到了一个新的农场，有时候他会回去看他的老朋友。但是他不想很快的回去，他喜欢欣赏沿途的风景，所以他会选择次短路，因为她知道一定有一条次短路。
这个乡村有R(1
Sample Input
4 4
1 2 100
2 4 200
2 3 250
3 4 100
Sample Output
450
Hint
两条路线：1 – > 2 – > 4（长度100 + 200 = 300）和1 – > 2 – > 3 – > 4（长度100 + 250 + 100 = 450）
题目链接
求从s到t的次短路径有两种情况：1、起点s到某个顶点u的最短路+d(u,t)。2、起点到某个顶点u的次短路+d(u,t)。
所以更新路径的时候需要把最短路径和次短路径两个都记录下来。
送一组数据
4 2
1 2 100
2 4 200
答案应该是500，然而如果初始化为0则答案会输出700。因为500的结果是又1到2，在从2返回1，再到2，再到4,100+100+100+200=500得到的；如果次短边初始化为0，则次短路径不再返回源点，而是在2与4之间折返，会偏大。
AC代码
Original: https://www.cnblogs.com/sky-stars/p/11354367.html
Author: Sky丨Star
Title: 【POJ 3255】Roadblocks（次短路 Dijkstra算法）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/611047/
转载文章受原作者版权保护。转载请注明原作者出处！