利用最短路的思想，最短路是维护每个节点到起点的最短距离，每次确定未确定里面距离最短的那个节点的最短距离，
根据次短路定义，从S到u的第二短的路线，那么只要维护一下次短路就可以了。新的节点次短路要么是S->u最短路+u->v
要么是 S->u次短路+ u->v 就是{d[e.to],d2[e.to] c+e.w}里面最短的是最短路 第二小的是次短路
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <set> 5 #include <algorithm> 6 #include <map> 7 #include <queue> 8 #include<vector> 9 #define maxn 5010 10 #define maxm 12500010 11 #define INF 0x3fffffff 12 using namespace std; 13 struct edge { 14 int to,w; 15 edge(){} 16 edge(int _to,int _w){ 17 to=_to;w=_w; 18 } 19 }; 20 typedef pair<int,int> P; 21 int V; 22 vector<edge> G[maxn]; 23 int d[maxn];//最短路 24 int d2[maxn];//次短路 25 void dijkstra(int s){ 26 priority_queue<P,vector<P>,greater<P> >q; 27 for(int i=0;i<V;++i){ 28 d[i]=INF; 29 d2[i]=INF; 30 } 31 d[s]=0; 32 q.push(P(d[s],s)); 33 while(!q.empty()){ 34 P p = q.top(); 35 q.pop(); 36 int v = p.second,c=p.first; 37 if(d2[v]<p.first)continue; 38 for(int i=0;i<G[v].size();++i){ 39 edge e = G[v][i]; 40 int c2 = c+e.w;//新的权值 41 if(d[e.to]>c2){//维护最短路 42 swap(d[e.to],c2); 43 q.push(P(d[e.to],e.to)); 44 } 45 if(d2[e.to]>c2&&d[e.to]<c2){//维护次短路 46 d2[e.to]=c2; 47 q.push(P(d2[e.to],e.to)); 48 } 49 } 50 } 51 } 52 int main (){ 53 int n,m; 54 while(scanf("%d%d",&n,&m)!=EOF){ 55 for(int i=0;i<n;++i)G[i].clear(); 56 V=n; 57 if(n==0&&m==0)break; 58 int u,v,w; 59 for(int i=0;i<m;++i){ 60 scanf("%d%d%d",&u,&v,&w); 61 G[u-1].push_back(edge(v-1,w)); 62 G[v-1].push_back(edge(u-1,w)); 63 } 64 dijkstra(0); 65 printf("%d ",d2[n-1]); 66 } 67 }