Cod sursa(job #1069269)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 29 decembrie 2013 18:13:40
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#include <vector>

using namespace std;

vector< pair<int,int> > v[30005];

int n,m,x,y,i,a,b,c;
int D[30005];
bool ok[30005];

void dfs(int x) {
    ok[x]=1;
    vector<pair<int,int> >::iterator it;
    for(it=v[x].begin();it!=v[x].end();it++) {
        if(ok[it->first])
            continue;
        if(x<it->first)
            D[it->first]=D[x]+it->second;
        else
            D[it->first]=D[x]-it->second;
        if(D[y])
            return;
        dfs(it->first);
    }
}

int main() {
    ifstream f("sate.in");
    ofstream g("sate.out");
    f>>n;
    f>>m;
    f>>x;
    f>>y;
    while(m) {
        f>>a>>b>>c;
        v[a].push_back(make_pair(b,c));
        v[b].push_back(make_pair(a,c));
        m--;
    }
    dfs(x);
    g<<D[y]<<"\n";
    f.close();g.close();
    return 0;
}