Dijkstra

模板：https://www.luogu.com.cn/problem/P3020

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+10;
const int INF=1e9;
int n,m;
struct abc
{
	int v,w,nex;
};
abc e[maxn*2];
int head[maxn],tot=0;
void add(int u,int v,int w)
{
	tot++;
	e[tot].v=v;
	e[tot].w=w;
	e[tot].nex=head[u];
	head[u]=tot;
	return ;
}
struct node
{
	int pos;
	int w;
	bool operator <( const node &x )const
    {
        return x.w < w;
    }
};
int dis[maxn];
bool vis[maxn];
priority_queue<node> q;
void init()
{
	for(int i=1;i<=n;i++)
	{
		dis[i]=INF;
		vis[i]=0;
	}
	return ;
}
void dijkstra()
{
	dis[1]=0;
	q.push((node){1,0});
	while(!q.empty())
	{
		node tmp=q.top();
		q.pop();
		int x=tmp.pos;
		if(vis[x])	continue;
		vis[x]=1;
		for(int i=head[x];i!=0;i=e[i].nex)
		{
			int y=e[i].v;
			if(dis[y]>dis[x]+e[i].w)
			{
				dis[y]=dis[x]+e[i].w;
				if(!vis[y])
				{
					q.push((node){y,dis[y]});
				}
			}
		}
	}
	return ;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	init();
	dijkstra();
	printf("%d\n",dis[n]);
    return 0;
}