Description

【题意】
给定 $N$ 个点 、$M$ 条无向边的无向图，求点 $1$ 至点 $N$ 的次短路长度。注：边可以重复走。

【输入格式】
第一行两个整数 $N、M$（$1 \le N \le 5000 ，1 \le M \le 10^5$）。
下来 $M$ 行，每行包含三个整数 $x、y$ 、 $c$，表示一条连接 点$x$ 和点 $y$ 长度为 $c(1\le c \le 5000)$ 无向边。

【输出格式】
输出仅一个整数，表示次短路的长度。

【输入样例】
4 4
1 2 100
2 4 200
2 3 250
3 4 100

【输出样例】
450

【样例解释】
最短路：$1\rightarrow 2 \rightarrow 4$（长度为 100+200=300）
次短路：$1 \rightarrow 2 \rightarrow 3 \rightarrow 4$（长度为 100+250+100=450）

Hint

#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&#44;c=a[k].c;
        if(d1[y]&gt;d1[x]+c)
		{
            d2[y]=d1[y];
			d1[y]=d1[x]+c;
            if(v[y]==0)q.push(y)&#44;v[y]=1;
        }
        if(d2[y]&gt;d1[x]+c &amp;&amp; d1[y]&lt;d1[x]+c )
        {
        	d2[y]=d1[x]+c;
        	if(v[y]==0)q.push(y)&#44;v[y]=1;
        }
        if(d2[y]&gt;d2[x]+c )
        {
        	d2[y]=d2[x]+c;
        	if(v[y]==0)q.push(y)&#44;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;
}

</p>