Pro4

原始文件为 CPP 代码，本文是转换后的 Markdown 文件。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge
{
    int from,to,weight;
    Edge(int f,int t,int w):from(f),to(t),weight(w){}

    bool operator<(const Edge& e2)
    {
        return weight < e2.weight;
    }
};

const int maxn = 100005;
int parent[maxn];
vector<Edge> edge;

int find(int v)
{
    return parent[v] == v ? v : parent[v] = find(parent[v]);
}
int main()
{
    //freopen("in.txt","r",stdin);
    int n,m; scanf("%d%d",&n,&m);
    edge.clear();

    for (int i = 0; i <= n; ++i)
        parent[i] = i;

    for (int i = 0; i < m; ++i)
    {
        int from,to,weight;
        scanf("%d%d%d",&from,&to,&weight);
        edge.push_back(Edge(from,to,weight));
    }

    sort(edge.begin(),edge.end());
    int ans = 0;
    for (int i = 0; i < m; ++i)
    {
        int x = find(edge[i].from);
        int y = find(edge[i].to);

        if (x != y) { parent[x] = y; }

        if (find(1) == find(n))
        {
            ans = edge[i].weight;
            break;
        }
    }
    cout << ans << endl;
}