Cod sursa(job #1491902)

Utilizator gedicaAlpaca Gedit gedica Data 26 septembrie 2015 14:01:33
Problema Sate Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#include <vector>

using namespace std;

const int NMAX= 30000;

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

struct str
{
    int n, c;
};

vector<str> g[NMAX+1];
bool a[NMAX+1];
int d[NMAX+1];

void dfs(int nod)
{
    a[nod]= 1;
    for( int i= 0; i<(int)g[nod].size(); ++i )
    {
        if( a[ g[nod][i].n ]==1 ) continue;
        int auxn, auxc;
        auxn= g[nod][i].n;
        auxc= g[nod][i].c;
        if( nod < auxn )
        {
            d[auxn]= d[nod] + auxc;
        }
        else d[auxn]= d[nod] - auxc;
        dfs(auxn);
    }
}

int main(  )
{
    int N, M, X, Y;
    in >> N >> M >> X >> Y;

    for( int i= 1; i<=M; ++i )
    {
        int x, y, co;
        str aux1, aux2;
        in >> x >> y >> co;
        aux1.n= x;
        aux2.n= y;
        aux1.c= aux2.c= co;
        g[x].push_back( aux2 );
        g[y].push_back( aux1 );
    }

    for( int i= 1; i<=N; ++i )
    {
        if( a[i]==0 )
            dfs( i );
    }

    out << d[Y] << '\n';

    return 0;
}