某街区有R条道路，N个路口。道路可以双向通行，问1号路口到n号路口的次短路长度是多少，同一条边可以经过多次。
dijkstra的堆优化可以求出最短路。到某个顶点v的次短路要么是到其他某个顶点u的最短路加上u->v的边，要么是到u的次短路加上u->v的边。
#include<iostream> #include<cstring> #include<algorithm> #include<cstring> #include<cstdio> #include<queue> using namespace std; const int MAXN=5010; const int MAXM=200010; const int inf=10000000; typedef pair<int,int> PII; int N,R; priority_queue<PII,vector<PII>,greater<PII> >q; struct edge { int v,nxt,w; } e[MAXM]; int head[MAXN],cnt=1; int dist[MAXN]; int dist2[MAXN]; void add(int u,int v,int w) { e[cnt].v = v; e[cnt].w = w; e[cnt].nxt = head[u]; head[u] = cnt++; } int dij(int S) { for(int i=1; i<=N; i++) { dist[i]=dist2[i]=inf; } int u; q.push(PII(dist[S]=0,S)); while(!q.empty()) { PII t = q.top();q.pop(); if(dist2[u=t.second]<t.first) continue; for(int i=head[u]; ~i; i=e[i].nxt) { int v=e[i].v,temp = t.first+e[i].w; if(dist[v]>temp) { swap(dist[v],temp); q.push(PII(dist[v],v)); } if(dist2[v]>temp&&dist[v]<temp) { q.push(PII(dist2[v]=temp,v)); } } } return dist2[N]; } int main() { memset(head,-1,sizeof head); scanf("%d%d",&N,&R); for(int i=1; i<=R; i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } cout<<dij(1)<<endl; return 0; }