一、思想：

求次短路，可以通过求最短路得到次短路长度

1到n的次短路长度必然产生于：从1走到x的最短路 + edge[x][y] +  y到n的最短路

首先预处理好1到每一个节点的最短路，和n到每一个节点的最短路

然后枚举每一条边作为中间边（x，y）或者（y，x），如果加起来长度等于最短路长度则跳过，否则更新。

从1走到x的最短路 + edge[x][y] +  y到n的最短路  给dist[n] 比较 找大于dist[n] 且是最小的那一个 

两遍spfa+暴力枚举

luogu 2865 次短路模板

#include
     
      #define rep(i,x,y) for(register int i=x;i<=y;i++)using namespace std;const int N=5050;const int M=100050;const int inf=0x3f3f3f3f;inline int read(){    int x=0,f=1;char ch=getchar();    while(!isdigit(ch)){
   if(ch=='-')f=-1;ch=getchar();}    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}    return x*f;}    int head[N],tot,vis[N],dis[N],dis2[N],n,m;struct node{
   int u,v,next,w;}e[M<<1];void insert(int u,int v,int w){    e[++tot]=(node){u,v,head[u],w};head[u]=tot;    e[++tot]=(node){v,u,head[v],w};head[v]=tot;}void spfa(int s,int d[]){    queue
      
       q;    d[s]=0;q.push(s);vis[s]=1;    while(!q.empty()){        int u=q.front();q.pop();vis[u]=0;        for(int i=head[u];i;i=e[i].next){            int v=e[i].v,w=e[i].w;            if(d[v]>d[u]+w){                d[v]=w+d[u];                if(!vis[v])                q.push(v),vis[v]=1;            }        }    }}int u,v,w,ans;int main(){    n=read();m=read();    memset(dis,inf,sizeof dis);    memset(dis2,inf,sizeof dis2);    rep(i,1,m){        u=read(),v=read(),w=read();        insert(u,v,w);}    spfa(1,dis);    spfa(n,dis2);    ans=inf;    rep(i,1,n)        for(int j=head[i];j;j=e[j].next){           int v=e[j].v,w=e[j].w;           if(dis[n]