dijkstra求次短路

赶紧来水一篇

用dijkstra求最短路相信大家都十分熟悉，而次短路似乎就有些陌生，但其实并不难理解。

求法：求次短路的求法与建最短路图十分类似。从起点与终点分别跑一遍最短路，设从起点到点i的距离为dis1[i]，从终点到点i的距离为dis2[i]。后枚举每一条边，设这条边相连u,v两点，这条边的权值为val。那么如果dis1[u] + dis[v] + val > dis1[终点]，那么这条边便不属于最短路上的边，这样dis1[u] + dis[v] + val的最小值便是次短路。

放一道模板题：poj3255（http://poj.org/problem?id=3255）

代码如下：

 1 #include<cstdio>
 2 #include<queue>
 3 #include<algorithm>
 4 #define ma make_pair
 5 #define fir first
 6 #define sec second
 7 #define pa pair<int,int>
 8 using namespace std;
 9 
10 const int maxn=100005;
11 int n,m,dis1[maxn],dis2[maxn],vis[maxn],ans;
12 int tot,hed[maxn*2],nxt[maxn*2],to[maxn*2],val[maxn*2];
13 priority_queue <pa,vector<pa>,greater<pa> > heap;
14 
15 int read(void) {
16     char c; while (c=getchar(),c<'0' || c>'9'); int x=c-'0';
17     while (c=getchar(),c>='0' && c<='9') x=x*10+c-'0'; return x;
18 }
19 
20 void add(int x,int y,int v) {
21     nxt[++tot]=hed[x]; hed[x]=tot; 
22     to[tot]=y; val[tot]=v;
23 }
24 
25 void dijkstra(int s,int t,int *dis) {
26     for (int i=1;i<=n;++i) dis[i]=2e9,vis[i]=0;
27     dis[s]=0; heap.push(ma(0,s));
28     while (!heap.empty()) {
29       int u=heap.top().sec; heap.pop();
30         if (vis[u]) continue;
31       vis[u]=1;
32         for (int i=hed[u];i;i=nxt[i]) {
33           int v=to[i];
34             if (dis[u]+val[i]<dis[v]) {
35               dis[v]=dis[u]+val[i];
36               heap.push(ma(dis[v],v));
37             }
38         }
39     }
40 }
41 
42 int main() {
43     n=read(); m=read();
44       for (int i=1;i<=m;++i) {
45           int x=read(),y=read(),v=read();
46           add(x,y,v); add(y,x,v);
47       }  
48     dijkstra(1,n,dis1); //跑两次最短路 
49     dijkstra(n,1,dis2);
50     ans=2e9;
51       for (int i=1;i<=n;++i)
52         for (int j=hed[i];j;j=nxt[j]) {
53           int v=to[j];
54           if (dis1[i]+dis2[v]+val[j]>dis1[n]) //取不是最短路上边的最小值 
55             ans=min(ans,dis1[i]+dis2[v]+val[j]);
56         }
57     printf("%d",ans);
58     return 0;
59 }