SPFA，链式前向星存图

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
struct edge{
	long long u,v,w,next;
}g[200001];
long long n,m,u,v,w,d[200001],tot,head[200001];
bool inque[20001];
queue<long long> q;
void addedge(long long u,long long v,long long w){
	g[++tot].u=u;
	g[tot].v=v;
	g[tot].next=head[u];
	g[tot].w=w;
	head[u]=tot;
	return;
}
void spfa(long long s){
	memset(d,0x3f3f3f,sizeof(d));
	d[s]=0;
	q.push(s);
	while(!q.empty()){
		long long u=q.front();
		q.pop();
		inque[u]=0;
		for(long long i=head[u];i!=-1;i=g[i].next){
			long long v=g[i].v;
			long long w=g[i].w;
			if(d[u]+w<d[v]){
				d[v]=d[u]+w;
				if(!inque[v]){
					q.push(v);
					inque[v]=1;
				}
			}
		}
	}
	return;
}
int main(){
	cin>>n>>m;
	memset(head,-1,sizeof(head));
	for(long long i=1;i<=m;i++){
		cin>>u>>v>>w;
		addedge(u,v,w);
		addedge(v,u,w);
	}
	spfa(1);
	cout<<d[n];
	return 0;
}