Cod sursa(job #2781539)

Utilizator DragosC1Dragos DragosC1 Data 9 octombrie 2021 19:03:25
Problema PScNv Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

struct dt {
    int x, y, k;
};

dt mch[500001];
int n, m, X, Y;

void read() {
    int i;
    ifstream f("pscnv.in");
    f >> n >> m >> X >> Y;
    for (i = 1; i <= m; i++) 
        f >> mch[i].x >> mch[i].y >> mch[i].k;
    f.close();
}

bool csort(dt a, dt b) {
    if (a.k < b.k)
        return 1;
    return 0;
}

int t[250001];

int rad(int x) {
    if (x == t[x])
        return x;
    else return t[x] = rad(t[x]);
}

void unite(int x, int y) {
    if (t[x] < t[y])
        t[y] = t[x];
    else t[x] = t[y];
}

int rez;

void solve() {
    int i, r1, r2;
    sort(mch + 1, mch + m + 1, csort);
    for (i = 1; i <= n; i++)
        t[i] = i;
    for (i = 1; i <= m; i++) {
        r1 = rad(mch[i].x), r2 = rad(mch[i].y);
        if (r1 != r2)
            unite(r1, r2);
        if (rad(X) == rad(Y)) {
            rez = mch[i].k;
            break;
        }
    }
}

void output() {
    ofstream g("pscnv.out");
    g << rez;
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}