Cod sursa(job #1109024)

Utilizator felixiPuscasu Felix felixi Data 16 februarie 2014 17:23:24
Problema Sate Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream in("sate.in");
ofstream out("sate.out");

const int NMAX= 30000;

struct GRAF{
    int vf, cost;
};

vector <GRAF> d[NMAX+1];
bool viz[NMAX+1];
int Rasp= 0, gata= 1, X, S;

void dfs(int nod){
    viz[ nod ]= 1;
    int lg= (int)d[nod].size();
    for(int i=0; i<lg; i++){
        int x= d[nod][i].vf, y= d[nod][i].cost;
        if( viz[x]==0 ){
            if(x>nod) Rasp+= y*gata;
            else Rasp-= y*gata;
            if( x==S ) gata= 0;
            dfs( x );
        }
    }
    viz[ nod ]= 0;
}

int main()
{
    int N,M, a,b,c;
    GRAF nr;
    in>>N>>M>>X>>S;
    for(int i=1; i<=N; i++){
        in>>a>>b>>c;
        nr.vf= b;  nr.cost= c;
        d[a].push_back(nr);
        nr.vf= a;
        d[b].push_back(nr);
    }
    dfs( X );
    out<<Rasp<<'\n';
    in.close();
    out.close();
    return 0;
}