题意：求1-n次短路。
思路：就是次短路模板题，这里用dijstra写的，只要用另一个数组存次短距离即可，每次将最短路，和次短路都放入队列中，这样更新最短路，次短路更新就是 该距离大于最短，小于次短就更新。
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<queue> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; ll d[5050],d2[5050]; struct edge{ int u,v,w,next; }e[200100]; int head[5050],visit[5050],cnt,n,r; struct node{ int id; ll dist; node(int _id=0,ll _dist=0):id(_id),dist(_dist){} bool operator < (const node &a)const{ return dist>a.dist; } }; void add(int u,int v,int w) { e[cnt].u=u; e[cnt].v=v; e[cnt].w=w; e[cnt].next=head[u]; head[u]=cnt++; } void dij() { for(int i=0;i<=n;i++) d[i]=d2[i]=inf; priority_queue<node> q; while(!q.empty()) q.pop(); d[1]=0; q.push(node(1,0)); node p; while(!q.empty()) { p=q.top(); q.pop(); int u=p.id; ll dis=p.dist; if(d2[u]<dis) continue; for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].v; ll dd=dis+e[i].w; if(d[v]>dd) { swap(d[v],dd); q.push(node(v,d[v])); } if(d2[v]>dd&&dd>d[v]) { d2[v]=dd; q.push(node(v,d2[v])); } } } } int main() { int u,v,w; cnt=0; memset(head,-1,sizeof(head)); scanf("%d%d",&n,&r); for(int i=0;i<r;i++) { scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } dij(); printf("%lld ",d2[n]); return 0; }