Cod sursa(job #2691240)

Utilizator denisa.iordacheIordache Denisa-Elena denisa.iordache Data 27 decembrie 2020 17:25:56
Problema PScNv Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int NMAX = 250010;
const int MMAX = 500010;
int n,m,x,y,t[NMAX];
struct muchie
{
    int s, d, c;
} G[MMAX];

bool cmp ( muchie a, muchie b)
{
    return a.c < b.c;
}

int parent (int nod)  //functie pentru determinarea inceputului unei componente conexe
{
    while (t[nod]!=nod)
        nod = t[nod];
    return nod;

}


int main() {
    ifstream f("pscnv.in");
    ofstream g("pscnv.out");
    f>>n>>m>>x>>y;
    for(int i=0;i<m;i++)
    {
        f>>G[i].s>>G[i].d>>G[i].c;
    }
    sort(G,G+m,cmp);

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

    /*for(int i=0;i<m;i++)
        cout<<G[i].s<<" "<<G[i].d<<" "<<G[i].c<<endl;*/

        for(int i=0;i<m;i++) {


        if (parent(G[i].s) != parent(G[i].d)) //daca nodurile nu fac parte din aceeasi componenta conexa
            t[G[i].d] = G[i].s;
        if(parent(x) == parent(y))
        {
            g<<G[i].c;
            break;
        }


    }
    f.close();
    g.close();

    return 0;
}