1.题目描述：
2.思路总结：
a.读完题目后分析发现，从题目给我们的数据，我们可以抽象出来一个图结构。题目要求从S到T使的权重最小，很明显，这是一个最小生成树的问题，接下来我们判断使用普利姆算法还是克鲁斯卡尔算法，首先这道题不是一个连通图，并且会中途停止，以边为中心，所以我们选择克鲁斯卡尔算法。
b.算法明确以后，我们看看有什么特别之处，刚开始我建立了一个邻接表，但是我发现这道题不用邻接表就可以做，建立一个{{w，u，v}}的二维数组后，对数组中的元素按权重从小到大排序，依次加入每个边，并切用并查集查找，防止形成环，当s和t第一次联通时，最后加入的这个边的权重就是最小路劲的最大的边权，因为我们时从小到大依次加入的。
3.代码：
include
include
include
include
using namespace std;
vector
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
int main() {
int n, m, s, t;
vector<tuple<int, int, int>> p;
cin >> n >> m >> s >> t;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
p.push_back({w, u, v});
}
sort(p.begin(), p.end());
parent.resize(n + 1);
for (int i = 1; i <= n; i++) parent[i] = i;
int a = 0;
for (auto& e : p) {
int w = get<0>(e);
int u = get<1>(e);
int v = get<2>(e);
int ru = find(u), rv = find(v);
if (ru != rv) {
parent[ru] = rv;
if (find(s) == find(t)) {
a = w;
break;
}
}
}
cout << a << endl;
return 0;
}