C++14(g++5.4) 解法, 执行用时: 154ms, 内存消耗: 3348K, 提交时间: 2019-06-27 20:10:49

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n,m;
const int maxn=5005;
const int INF=0x3f3f3f3f;
int dis[maxn],dis2[maxn];
struct edge 
{
	int u,w;
};
typedef pair<int,int>P;
priority_queue<P, vector<P>, greater<P> >pq;
vector<edge>ed[maxn];
void init()
{
	for(int i=1;i<=n;i++)
	{
		ed[i].clear();
		dis[i]=dis2[i]=INF;
	}
}
void dtwo(int u)
{
	dis[u]=0;
	pq.push(P(u,0));
	while(!pq.empty())
	{
		P p=pq.top();
		pq.pop();
		int v=p.first,d=p.second;
		if(dis2[v]<d)continue;
		for(unsigned i=0;i<ed[v].size();i++)
		{
			edge e=ed[v][i];
			int d2=d+e.w;
			if(dis[e.u]>d2)
		{
			 swap(dis[e.u],d2);
			 pq.push(P(e.u,dis[e.u]));
		}
			if(dis2[e.u]>d2&&dis[e.u]<d2)
			{
				dis2[e.u]=d2;
				pq.push(P(e.u,dis2[e.u]));
			}
		}
	}
}
int main()
{
	int ai,bi,ci;
	cin>>n>>m;
	init();
	for(int i=0;i<m;i++)
	{
		cin>>ai>>bi>>ci;
		ed[ai].push_back({bi,ci});
		ed[bi].push_back({ai,ci});
   }
	dtwo(1);
    cout<<dis2[n];
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 52ms, 内存消耗: 4516K, 提交时间: 2020-09-23 10:29:01

#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
using namespace std;
const int N=5e3+5,M=2e5+5;
struct Edge{int to,w,nxt;}e[M];
int n,m,fst[N],tote,mi[N],mi2[N];
priority_queue<pii>que;
void adde(int u,int v,int w){
	e[++tote]=(Edge){v,w,fst[u]};fst[u]=tote;
	e[++tote]=(Edge){u,w,fst[v]};fst[v]=tote;
}
void DIJ(){
	memset(mi,0x3f,sizeof(mi));memset(mi2,0x3f,sizeof(mi2));
	que.push(pii(0,1));mi[1]=0;
	while(!que.empty()){
		int u=que.top().second,ww=-que.top().first;que.pop();
		for(int i=fst[u],v,w;i;i=e[i].nxt){
			v=e[i].to,w=e[i].w;
			if(mi[v]>ww+w){
				mi2[v]=mi[v];mi[v]=ww+w;
				que.push(pii(-mi[v],v));que.push(pii(-mi2[v],v));
			}else if(mi2[v]>ww+w)mi2[v]=ww+w,que.push(pii(-mi2[v],v));
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,u,v,w;i<=m;i++)
		scanf("%d%d%d",&u,&v,&w),adde(u,v,w);
	DIJ();printf("%d\n",mi2[n]);
	return 0;
}