Cod sursa(job #2697078)

Utilizator Cibotaru.MateiMatei-Stefan Cibotaru Cibotaru.Matei Data 17 ianuarie 2021 17:19:33
Problema PScNv Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <algorithm>
#include <tuple>
using namespace std;

int parent(vector<int>& parents, int x) {
    if (parents[x] != x) {
        parents[x] = parent(parents, parents[x]);
    }
    return parents[x];
}

int main() {
    ifstream f("pscnv.in");
    int n, m, a, b;
    vector<tuple<int, int, int>> graph;
    f >> n >> m >> a >> b;
    vector<int> parents(n + 1);

    for (int i = 0; i < m; i++) {
        int x, y, k;
        f >> x >> y >> k;
        graph.push_back(make_tuple(k, x, y));
    }

    sort(graph.begin(), graph.end(), [](tuple<int, int, int> a, tuple<int, int, int> b) -> bool { return get<0>(a) < get<0>(b); });

    for (int i = 1; i <= n; i++) {
        parents[i] = i;
    }

    ofstream g("pscnv.out");

    for (auto& i : graph) {
        if (parent(parents, get<1>(i)) != parent(parents, get<2>(i))) {
            parents[get<2>(i)] = get<1>(i);
        }
        if (parent(parents, a) == parent(parents, b)) {
            g << get<0>(i);
            break;
        }
    }
}