题目链接:http://poj.org/bbs?problem_id=3255
思路:分别以源点1和终点N为源点,两次SPFA求得dist1[i](1到各点的最短距离)以及dist2[i](各点到N的最短距离),然后就是枚举边了,设某一条边的两端为u,v,权值为w,则dist1[u]+w+dist2[v]即为1->N的一条路径,在所有的路径中找出次短的即可。
2022-11-06 10:21:53
题目链接:http://poj.org/bbs?problem_id=3255
思路:分别以源点1和终点N为源点,两次SPFA求得dist1[i](1到各点的最短距离)以及dist2[i](各点到N的最短距离),然后就是枚举边了,设某一条边的两端为u,v,权值为w,则dist1[u]+w+dist2[v]即为1->N的一条路径,在所有的路径中找出次短的即可。