题目：求1到n的次短路径

#include <bits/stdc++.h>
using namespace std;
const int N=5100, M=2e5+10;
struct edge{int x, y, c, pre;}a[M];
int alen, last[N];
void ins(int x, int y, int c){
    alen++;
    a[alen]={x, y, c, last[x]};
    last[x]=alen;
}
int read()
{
    int x=0, f=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()){if(ch=='-')f=-1;}
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-48;
    return x*f;
}
int n, m, d1[N], d2[N], v[N];
void spfa()
{
    queue<int> q;
    q.push(1);
    memset(d1, 0x0f, sizeof(d1));
    d1[1]=0;
    memset(d2, 0x0f, sizeof(d2));
    memset(v, 0, sizeof(v));
    v[1]=1;
    
    while(!q.empty()){
        int x=q.front();
        q.pop();
        v[x]=0;
        for(int k=last[x];k;k=a[k].pre){
            int y=a[k].y, c=a[k].c;
            if(d1[y] > d1[x] + c){
                d2[y] = d1[y];
                d1[y] = d1[x] + c;
                if(v[y]==0) q.push(y), v[y]=1;
            }
            if(d2[y] > d1[x] + c && d1[y] < d1[x] + c){
                d2[y] = d1[x] + c;
                if(v[y]==0) q.push(y), v[y]=1;
            }
            if(d2[y] > d2[x] + c){
                d2[y] = d2[x] + c;
                if(v[y]==0) q.push(y), v[y]=1;
            }
        }
    }   
}
int main()
{
    n=read();
    m=read();
    alen=0;
    memset(last, 0, sizeof(last));
    for(int i=1, x, y, c; i<=m; i++){
        x=read();
        y=read();
        c=read();
        ins(x, y, c);
        ins(y, x, c);
    }
    spfa();
    printf("%d\n", d2[n]);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=5100,M=2e5+10;
struct edge{int x,y,c,pre;}a[M];int alen,last[N];
void ins(int x,int y,int c){alen++;a[alen]={x,y,c,last[x]};last[x]=alen;}
int read()
{
	int x=0,f=1;char ch=getchar();
	for(;!isdigit(ch);ch=getchar()){if(ch=='-')f=-1;}
	for(;isdigit(ch);ch=getchar()) x=x*10+ch-48;
	return x*f;
}
int n,m,d1[N],d2[N],v[N];
void spfa()
{
    queue<int> q;q.push(1);
    memset(d1,0x0f,sizeof(d1));d1[1]=0;
    memset(d2,0x0f,sizeof(d2));
    memset(v,0,sizeof(v));v[1]=1;
    
    while(!q.empty())
	{
        int x=q.front();q.pop();v[x]=0;
        for(int k=last[x];k;k=a[k].pre)
		{
            int y=a[k].y,c=a[k].c;
            if(d1[y]>d1[x]+c)
			{
                d2[y]=d1[y];
				d1[y]=d1[x]+c;
                if(v[y]==0)q.push(y),v[y]=1;
            }
            if(d2[y]>d1[x]+c && d1[y]<d1[x]+c )
            {
            	d2[y]=d1[x]+c;
            	if(v[y]==0)q.push(y),v[y]=1;
            }
            if(d2[y]>d2[x]+c )
            {
            	d2[y]=d2[x]+c;
            	if(v[y]==0)q.push(y),v[y]=1;
            }
        }
    }   
}
int main()
{
    n=read();m=read();
    alen=0;memset(last,0,sizeof(last));
    for(int i=1,x,y,c;i<=m;i++)
	{
        x=read();y=read();c=read();
        ins(x,y,c);ins(y,x,c);
    }
    spfa();
    printf("%d\n",d2[n]);
    return 0;
}