看到要计算最短时间就知道要排序

并查集模板

cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Road {
    int from, to, repairTime;
};

vector<int> parent;

int find(int x) {
    if (parent[x] == x) {
        return x;
    }
    return parent[x] = find(parent[x]);
}

bool unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootX] = rootY;
        return true; // 返回 true 表示成功合并
    }
    return false; // 返回 false 表示已经在同一集合中
}

int main() {
    int N, M;
    cin >> N >> M;

    vector<Road> roads(M);

    for (int i = 0; i < N; ++i) {
        parent.push_back(i); // 初始化每个村庄独立成集合
    }

    for (int i = 0; i < M; ++i) {
        cin >> roads[i].from >> roads[i].to >> roads[i].repairTime;
        roads[i].from--;
        roads[i].to--;
    }

    sort(roads.begin(), roads.end(), [](const Road &a, const Road &b) {
        return a.repairTime < b.repairTime;
    });

    int components = N;
    int earliestTime = -1;

    for (int i = 0; i < M; ++i) {
        if (unite(roads[i].from, roads[i].to)) {
            components--;
            earliestTime = roads[i].repairTime;
            if (components == 1) {
                break; // 所有村庄已连通
            }
        }
    }

    if (components == 1) {
        cout << earliestTime << endl;
    } else {
        cout << -1 << endl;
    }

    return 0;
}