Cod sursa(job #1034076)

Utilizator usermeBogdan Cretu userme Data 17 noiembrie 2013 17:25:29
Problema Sate Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

queue<int> q;

struct sat{
    int x,d;
};

vector<sat> v[30001];

int e[30001];

void bfs(){
    while ( !q.empty() ){
        int x=q.front();
        for ( int i=0;i<v[x].size();++i ){
            if ( e[v[x][i].x]==-1 ){
                if ( v[x][i].x>x ){
                    e[v[x][i].x]=e[x]+v[x][i].d;
                    q.push(v[x][i].x);
                }
                else {
                    e[v[x][i].x]=e[x]-v[x][i].d;
                    q.push(v[x][i].x);
                }
            }
        }
        q.pop();
    }
}


int main()
{
    FILE*f=fopen("sate.in","r");
    FILE*h=fopen("sate.out","w");
    int n,m,x,y;
    fscanf(f,"%d%d%d%d",&n,&m,&x,&y);
    for ( int i=1;i<=n;++i )
        e[i]=-1;
    q.push(x);
    for ( int i=1;i<=m;++i ){
        int a,b,d;
        fscanf(f,"%d%d%d",&a,&b,&d);
        sat w;
        w.x=b;w.d=d;
        v[a].push_back(w);
        w.x=a;
        v[b].push_back(w);
    }
    e[x]=0;
    bfs();
    fprintf(h,"%d",e[y]);
    return 0;
}