Cod sursa(job #3372918)

Utilizator lea_Lea Ales lea_ Data 5 noiembrie 2026 15:10:11
Problema Sate Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>

using namespace std;


const int maxn =30005;
int parent[maxn];
long long dist[maxn];

int find(int i){
    if(parent[i]==i)
        return i;
    int root=find(parent[i]);
    dist[i]+=dist[parent[i]];
    return parent[i]=root;
}

bool unite(int i, int j, long long d){
    int root_i=find(i);
    int root_j=find(j);

    if(root_i != root_j){
        parent[root_j]=root_i;
        dist[root_j]=dist[i]+d-dist[j];
        return true;
    }
    return false;
}

int main(){
    int n, m, x, y;
    ifstream fin("sate.in");
    ofstream fout("sate.out");
    if (!(fin >> n >> m >> x >> y)) return 0;

    for(int i=1; i<=n; ++i){
        parent[i]=i;
        dist[i]=0;
    }

    for(int k=0; k<m; ++k){
        int i, j;
        long long d;
        fin>>i>>j>>d;
        unite(i, j, d);
    }
    find(x);
    find(y);

    fout<<abs(dist[y]-dist[x]);
    return 0;
}