题目描述
给出一张图，求它从1到n的严格次短路的长度。
思路
我们可以在求最短路时维护两个数组，一个是dis[v]表示到v的最短路的长度，另一个是scd[v]表示到v的次短路，每次更新节点时我们可以判断并保证scd[v]一定严格小于dis[v]。由于长度一定为正，我们可以用Dijkstra求最短路。
代码
#include <bits/stdc++.h> using namespace std; const int N=6000,M=1e5+10; int nxt[M<<1],head[N],to[M<<1],w[M<<1],tot,dis[N],scd[N]; void add_edge(int x,int y,int v) { nxt[++tot]=head[x]; head[x]=tot; to[tot]=y; w[tot]=v; } void Dijkstra() { memset(dis,0x3f,sizeof(dis)); memset(scd,0x3f,sizeof(scd)); priority_queue<pair<int,int> >q; dis[1]=0;q.push(make_pair(0,1)); while(!q.empty()) { int u=q.top().second,m=-q.top().first;q.pop(); if(m>scd[u])continue ; for(int i=head[u];i;i=nxt[i]) { int v=to[i],ss=m+w[i]; if(dis[v]>ss) { swap(dis[v],ss); q.push(make_pair(-dis[v],v)); } if(scd[v]>ss&&ss!=dis[v]) { scd[v]=ss; q.push(make_pair(-scd[v],v)); } } } } int main() { int n,r; scanf("%d%d",&n,&r); for(int i=1;i<=r;i++) { int a,b,d; scanf("%d%d%d",&a,&b,&d); add_edge(a,b,d); add_edge(b,a,d); } Dijkstra(); printf("%d",scd[n]); return 0; }
原文：https://www.cnblogs.com/fangbozhen/p/11681079.html