Cod sursa(job #1700063)

Utilizator NastureNasture Anca Nasture Data 9 mai 2016 11:44:33
Problema Sate Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
vector <pair <int,int> > L[100005];
queue <int> coada;
int n,s,viz[100005],mini[100005],val,x,y;
void citire(){
    int n1,n2,m,val;
    scanf("%d%d%d%d",&n,&m,&x,&y);
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&n1,&n2,&val);
        L[n1].push_back(make_pair(n2,val));
        L[n2].push_back(make_pair(n1,-val));
    }
}
void dfs(int s){
    coada.push(s);
    int primul,nod;
    viz[s]=1;
    int ok=0;
    while(!coada.empty()&&ok==0){
        primul=coada.front();
        coada.pop();
        vector <pair <int,int> >:: iterator it;
        for(it=L[primul].begin();it!=L[primul].end();++it){
            pair<int,int> nod;
            nod=*it;
            if(viz[nod.first]==0){
                val=val+nod.second;
                coada.push(nod.first);
                viz[nod.first]=1;
                if(y==nod.first)
                    ok=1;
            }
        }

    }
}
int main(){
    freopen("sate.in","r",stdin);
    freopen("sate.out","w",stdout);
    citire();
    dfs(x);
    printf("%d",val);
    return 0;
}