迪杰斯特拉

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

struct Node{
	// 边的终点、权值
	int to, val;
};
vector<Node> g[100005];
// 标记数组
bool vis[100005];
// 距离数组
int dist[100005];
int n, m;

// 迪杰斯特拉
void Dijkstra(int x){
	// 初始化起点到其余任何一个点的最短距离
	memset(dist, 0x3f, sizeof dist);
	// 自己到自己的距离 初始化为0
	dist[x] = 0;
	// 结束标志：所有的节点都被标记
	while(1){
		// 在未标记的节点中，找一个距离起点最近的节点，作为中转节点
		// mi维护最短距离    k维护节点编号
		int mi = 0x3f3f3f3f, k = -1;
		// 遍历dist数组，找最小值 对应的编号
		for(int i=1;i<=n;i++){
			if(vis[i]==0 && dist[i]<mi){
				mi = dist[i];
				k = i;
			}
		}
		// k = -1 说明上面没有找到满足要求的中间节点，即所有的节点都被标记了
		if(k == -1) break;
		// 以节点k作为中间节点，去更新起点到其它节点的最短距离
		// 原本要求 x 到 y 的最短距离： x -> y
		// 以k作为中间节点，计算 x 到 k 和 k 到 y 的距离：x -> k -> y
		// 因为 x -> k 已知，只需要遍历k能到的节点即可
		for(int i=0;i<g[k].size();i++){
			// k能到的节点：g[k][i].to  权值：g[k][i].val
			int y = g[k][i].to;
			// x -> k 的距离为：dist[k]
			// k -> y 的距离为：g[k][i].val
			
			// 计算 x -> y的距离：
			// 情况1：x -> y ：dist[y]
			// 情况2：x -> k -> y： dist[k] + g[k][i].val
			dist[y] = min(dist[y], dist[k] + g[k][i].val);
		}
		vis[k] = 1;
	}
}

int main(){
	int a, b;
	cin>>n>>m>>a>>b;
	for(int i=1;i<=m;i++){
		int x, y, z;
		// x --> y 权值为 z
		cin>>x>>y>>z;
		g[x].push_back({y, z});
		g[y].push_back({x, z});
	}
	Dijkstra(a);
	cout<<dist[b];
	return 0;
}