题解 | #【模板】单源最短路2#

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
typedef struct node{
	int x, w;	//可到达点编号，权重 
	bool operator <(const struct node o) const{
		return w>o.w;    //重载<号，使得权重小的优先出队列
	}
}N;
int n, m, dist[50001];
vector<N> g[50001];	//邻接表 

void dijkstra(int x){
	bool vis[50001];
	memset(vis, false, sizeof(vis));
	memset(dist, 0x7f, sizeof(dist));
	priority_queue<N> q;
	q.push((N){x, 0});
	dist[x] = 0;
	while(!q.empty()){
		N t = q.top();
		q.pop();
		if(vis[t.x])
			continue;
		vis[t.x] = true;
		for(int i=0; i<g[t.x].size(); i++){
			if(dist[t.x]+g[t.x][i].w<dist[g[t.x][i].x]){
				dist[g[t.x][i].x] = dist[t.x]+g[t.x][i].w;
				q.push((N){g[t.x][i].x, dist[g[t.x][i].x]});
			}
		}
	}
}
int main(){
	scanf("%d%d", &n, &m);
	for(int i=0; i<m; i++){
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		g[u].push_back((N){v, w});
		g[v].push_back((N){u, w});
	}
	dijkstra(1);
	if(dist[n]==0x7f7f7f7f)
		cout<<-1;
	else
		cout<<dist[n];
	return 0;
}