Cod sursa(job #343410)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 25 august 2009 19:05:22
Problema Sate Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <stdio.h>
#include <vector>
#define Nmax 30005
#define Mmax 100025
using namespace std;

vector<pair <int,int> > A[Nmax];
int use[Nmax],c[Mmax+10],d[Nmax];
int n,m,x,y,i,s1,s2,dd,p,u;

int main(){
	freopen("sate.in","r",stdin);
   freopen("sate.out","w",stdout);
   scanf("%d%d%d%d",&n,&m,&x,&y);
   for(i=1;i<=n;++i){
   	scanf("%d%d%d",&s1,&s2,&dd);
      A[s1].push_back(make_pair(s2,dd));
      A[s2].push_back(make_pair(s1,-dd));
   }

   use[x]=1;
   c[1]=x; p=1; u=1;
   vector< pair<int,int> >:: iterator it;
   while(p<=u){
               use[c[p]]=1;
               for(it=A[c[p]].begin(); it!=A[c[p]].end(); it++)
                 if(!use[it->first]){
                   d[it->first] = d[c[p]] + it-> second;
                   c[++u] = it->first;
                   }
               p++;
               }
                   
   printf("%d\n",abs(d[y]));
   fclose(stdin); fclose(stdout);
   return 0;
}