最多有 $10^5$ 条带权无向边

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> v[100010];
int d[100010];
	int n,m;
const int inf=1e9;
void Dijkstra(int start)
{
	priority_queue<pair<int,int>>q;
	for(int i=0;i<=100000;i++)
	{
		d[i]=inf;
	}
	d[1]=0;
	q.push(make_pair(0,1));
	while(!q.empty())
	{
		pair<int,int> p=q.top();q.pop();
		int w=p.first;
		int u=p.second;
		if(w>d[u])
		{
			continue;
		}
		int l=v[u].size();
		for(int i=0;i<l;i++)
		{
			pair<int,int> op=v[u][i];
			int f=op.first;
			int s=op.second;
			if(f+w<d[s])
			{
				d[s]=f+w;
				q.push(make_pair(d[s],s));
			}
		} 
	}
	if(d[n]==inf)
	{
		cout<<-1;
	}
	else
	{
		cout<<d[n];
	}
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int a,b,w;
		scanf("%d%d%d",&a,&b,&w);
		v[a].push_back(make_pair(w,b));
		v[b].push_back(make_pair(w,a));
	}
	Dijkstra(1);
}