赶紧来水一篇
用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 }
转载于:https://www.cnblogs.com/Gaxc/p/9850948.html
