我想分别求出以起点为源点的单源最短路和以终点为源点的单源最短路，再枚举中间的点，这样找到第二最短路，但是有问题。。。80分。无奈。改成删边吧。

枚举删边就行。

不过用NOCOW上讲的记录第2短距离的方法就是不过，不知道怎么回事。

永远的60分,..而且错的3个都一样..

还好不是K短路,这样的话还好简单,SPFA求最短路,弄了一维树组G=J表示1到I通过J最短,然后递归求出路径,每次删掉一条边,再求最段路. 哪为大牛能把K短路的原理发给我,谢了.

[ftc=#FF0000]■[ftc=#C81010]■ ■[ftc=#9A0202]■ ■

楼下好强

先用Dijkstra求出第一个点到最后一个点的最短路径.并记下路径.

然后循环分别删除路径.找到一个最值.

值得注意的是如果删除路径的时候找到的值等于第一长的,而又找到另一个比它大,依题意应该覆盖~.

用SPFA先算出最短路,再枚举删边,再SPFA,数据再大点也是0MS

O(n^2logn).应该可以过的.

好弱的数据……O(N^2)的Dijkstra都OmsAC.

这怎么算？？？？？？

DIJKSTRA 然后 枚举删边

正确的方法应该是N-1次DIJKSTRA，但是我用1次的FLOYED过了7个点……

Dijkstra..删除第一短路上的边..然后Dijkstra...

ycglovewxx说的方法是很好的

Soleadad

没看懂题目吧,我想你没过这题

实在不行可以枚举.........

先求出最短路,然后尝试删除最短路上的每一条边,再做一次最短路,然后取最小值....就是第二短路了.........

嘘,一般人我才告诉他.

怎么做的？？？怎么算第2短呢？？？

既然n

DIJKSTRA

然后把得到的distance[]排个序

输出distance[2]就成了