次短路 输入

5 10
1 2 3355
2 3 1712
1 4 4892
1 5 1442
5 3 4768
3 1 4334
2 1 4365
3 1 2591
2 1 3817
3 2 4068

答案输出

4326

代码输出

7359

#include<bits/stdc++.h>  
using namespace std; 
struct AA
{
	int to,nex,w; 
}e[500010];
int head[500010],idx,dis[5][500010],n,m;
void add(int u,int v,int w)
{
	idx++;
	e[idx].nex=head[u];
	e[idx].to=v;
	e[idx].w=w;
	head[u]=idx;
} 
void Dijkstra2()
{
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
	memset(dis,0x3f,sizeof(dis));
	dis[0][1]=0;
	dis[1][1]=0;
	q.push({0,1});
	while(q.size())
	{
		pair<int,int > x=q.top();
		q.pop();
		int u=x.second,d=x.first;
		if(d>dis[1][u])continue;
		for(int i=head[u];i;i=e[i].nex)
		{
			int v=e[i].to;
			int w=e[i].w;
			if(dis[0][v]>d+w)
			{
				dis[1][v]=dis[0][v];
				dis[0][v]=d+w;  
				q.push({d+w,v});
				
			}
			if(dis[1][v]>d+w&&dis[0][v]<d+w)
			{
				dis[1][v]=d+w; 
				q.push({d+w,v});
			}
		}
	}
	
}
int main()
{  
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
		add(b,a,c);
	}
	Dijkstra2();
	cout<<dis[1][n];
    return 0;
}