poj 3255(次短路)

题目链接: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的一条路径,在所有的路径中找出次短的即可。

http://paste.ubuntu.com/5920862/

上一篇:[Git]解决Permission denied, please try again问题


下一篇:window系统查看端口被哪个进程占用