https://old.ynoip.cn/p/2607

#include <cstdio>
#include <cstring>
int n, m, s, e;
int map[2505][2505];

void add(int a, int b, int c);
void init(void);
int Dijkstra(int start, int end);

int main(void) {
	std::scanf("%d%d%d%d", &n, &m, &s, &e);

	init();
	for (int i = 1, a, b, c; i <= m; i++) {
		std::scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
	}
	std::printf("%d", Dijkstra(s, e));

	return 0;
}

void add(int a, int b, int c) {

	map[a][b] = c;
	map[b][a] = c;

	return;
}

void init(void) {

	memset(map, -1, sizeof(map));

	return;
}

int Dijkstra(int start, int end) {
	int distance[2505];
	memset(distance, 0x3f3f3f3f, sizeof(distance));
	distance[start] = 0;
	bool viewed[2505];
	memset(viewed, false, sizeof(viewed));
	int p = start;
	int dis = 0x3f3f3f3f;

	for (int i = 1; i < n; i++) {

		for (int u = 1; u <= n; u++) {
			if (!viewed[u] && distance[u] < dis) {
				p = u;
				dis = distance[u];
			}
		}

		viewed[p] = true;

		for (int u = 1; u <= n; u++) {
			if (!viewed[u] && map[p][u] != -1 && distance[p] + map[p][u] < distance[u]) {
				distance[u] = distance[p] + map[p][u];
			}
		}
		dis = 0x3f3f3f3f;
	}

	return distance[end];
}