图论：次短路

对于Dijkstra判断中取出的每一个点，如果到它的最短距离大于当前该点的次短距离，则当前该点已经取到最短距离和次短距离，不进行操作
否则进行两次判断：
如果小于最短边，则赋给最短边，并将最短边赋给次短边
或者如果大于最短边且小于次短边，则赋给次短边。两次完成之后均要加入队列

 1 #include<cstdio>
 2 #include<queue>
 3 #include<cstring>
 4 using namespace std; 
 5 const int INF=0x3f3f3f3f;
 6 const int maxn=5005;
 7 const int maxm=200005;
 8 int n,m,cnt;
 9 int g[maxn],d[maxn],d2[maxn];
10 struct Edge{int u,t,w,next;}e[maxm];
11 struct HeapNode{int d,u;bool operator <(const HeapNode& x) const{return d>x.d;}};
12 priority_queue<HeapNode> q;
13 void addedge(int x,int y,int z)
14 {
15     cnt++;e[cnt].u=x;e[cnt].t=y;e[cnt].w=z;
16     e[cnt].next=g[x];g[x]=cnt;
17 }
18 void dijkstra(int s)
19 {
20     for(int i=0;i<=n;i++) d[i]=d2[i]=INF;
21     d[s]=0;
22     HeapNode p;
23     p.d=0;p.u=s;
24     q.push(p);
25     while(!q.empty())
26     {
27         HeapNode x=q.top(); q.pop();
28         int u=x.u;
29         if(d2[u]<x.d) continue;
30         for(int tmp=g[u];tmp;tmp=e[tmp].next)
31         {
32             int dis=x.d+e[tmp].w;
33             if(d[e[tmp].t]>dis)
34             {
35                 swap(d[e[tmp].t],dis);
36                 p.d=d[e[tmp].t];p.u=e[tmp].t;
37                 q.push(p);
38             }
39             if(d2[e[tmp].t]>dis&&d[e[tmp].t]<dis)
40             {
41                 d2[e[tmp].t]=dis;
42                 p.d=d2[e[tmp].t];p.u=e[tmp].t;
43                 q.push(p);
44             }
45         }
46     }
47 }
48 void init()
49 {
50     cnt=0;
51     memset(g,0,sizeof(g));
52     while(!q.empty()) q.pop();
53 }
54 int main()
55 {
56     int u,v,w;
57     while(scanf("%d%d",&n,&m)==2)
58     {
59         init();
60         for(int i=1;i<=m;i++)
61         {
62             scanf("%d%d%d",&u,&v,&w);
63             addedge(u,v,w);
64             addedge(v,u,w);
65         }
66         dijkstra(1);
67         printf("%d
",d2[n]);
68     }
69     return 0;
70 }