Comment

Huhu_Miao: 2024-12-02 21:24:01
/**
 *    孩子们，暴力真的有用。(n^2 dijkstra)
 *    author:  Huhu_Miao
 *    created: 2024.12.2 21:21:00 (UTC+8)
**/
#include<bits/stdc++.h>

using pii = std::pair<int,int>;

void solve(){
	int n,E,s,t;
	std::cin >> n >> E >> s >> t;
	std::vector<std::vector<pii>> g(n+1,std::vector<pii>(0));
	for(int i = 0 ; i < E ; i++){
		int from, to , w;
		std::cin >> from >> to >> w;
		g[from].emplace_back(to,w);
		g[to].emplace_back(from,w);
	}

	std::deque<bool> vis(n+1,false);
	std::vector<int> dis(n+1,0x3f3f3f3f);
	dis[s] = 0;
	for(int i = 0 ; i < n ; i++){
		//find min in T
		int Tmin = 0; int min = 0x3f3f3f3f;
		for(int j = 1 ; j < n+1 ; j++){
			if(!vis[j] && dis[j] < min){
				Tmin = j;
				min = dis[j];
			}
		}
		if(dis[Tmin] == 0x3f3f3f3f) break;
		vis[Tmin] = true;
		for(const auto & [to,w] : g[Tmin]) dis[to] = std::min(dis[to],dis[Tmin] + w);
		
	}
	if(dis[t] == 0x3f3f3f3f)std::cout << -1 << '\n';
	else std::cout << dis[t] << '\n';
}

int main(){
	std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
	int T; std::cin>>T;
	while(T--) solve();
	return 0;
}