次短路模版题。贴个代码
#include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <cmath> #include <cstring> #include <queue> #include <set> #include <vector> #include <stack> #include <map> #include <iomanip> #define PI acos(-1.0) #define Max 1000005 #define inf 1<<28 #define LL(x) (x<<1) #define RR(x)(x<<1|1) using namespace std; int n,m; int num; int head[Max]; int dis[Max][2]; bool visit[Max][2]; struct kdq { int v,len,next; } edge[Max]; void insert(int u,int v,int len) { edge[num].len=len; edge[num].v=v; edge[num].next=head[u]; head[u]=num++; } void init() { memset(head,-1,sizeof(head)); memset(visit,0,sizeof(visit)); num=0; } void spfa(int s,int e,int k) { int i,j; for(i=1; i<=n; ++i) dis[i][k]=inf; dis[s][k]=0; visit[s][k]=1; queue<int>q; q.push(s); while(!q.empty()) { int temp=q.front(); q.pop(); visit[temp][k]=0; for(i=head[temp]; i!= -1; i= edge[i].next) { int tt=edge[i].v; int ttt=edge[i].len; if(dis[tt][k]>dis[temp][k]+ttt) { dis[tt][k]=dis[temp][k]+ttt; if(!visit[tt][k]) { q.push(tt); visit[tt][k]=1; } } } } } int main() { int i,j,k,l; int a,b,s; scanf("%d%d",&n,&m); init(); while(m--) { scanf("%d%d%d",&a,&b,&s); insert(a,b,s); insert(b,a,s); } spfa(1,n,0); spfa(n,1,1); int ans=inf; //cout<<dis[n][1]<<endl; for(i=1; i<=n; i++) { for(j=head[i]; j!=-1; j=edge[j].next)//s--i + i--tt + tt--e 大于最短路的最小值 { int tt=edge[j].v; int ttt=edge[j].len; int temp=dis[i][0]+dis[tt][1]+ttt; if(temp>dis[n][0]&&ans>temp) ans=temp; } } printf("%d\n",ans); return 0; }