Cod sursa(job #293214)

Utilizator vladbBogolin Vlad vladb Data 1 aprilie 2009 08:31:53
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
 #include<fstream>  
   
 using namespace std;  
   
 ifstream fin("sate.in");  
 ofstream fout("sate.out");  
   
 struct nod { long v,dist;  
              nod *next;  
            } *v[30001];  
 long n,m,e,xx,yy,s[30001],pus[30001],d[30001];   
   
 void citire()    
 {   long i,x,y,z;    
     nod *nou;    
     fin>>n>>m>>xx>>yy;   
     for(i=1;i<=m;i++)    
     {   fin>>x>>y>>z;   
         if(x==xx) d[y]=z;  
         nou=new nod;    
         nou->v=y;    
         nou->dist=z;  
         nou->next=v[x];    
         v[x]=nou;    
         nou=new nod;    
         nou->v=x;    
         nou->dist=z;  
         nou->next=v[y];    
         v[y]=nou;    
     }    
 }    
   
 void bf(int nd)  
 {    long st=1,dr=1,i;  
      s[dr]=nd;  
      pus[nd]=1;  
      nod *p;  
      while(st<=dr)  
      {            p=v[s[st]];  
                   while(p!=NULL)  
                   {             if(pus[p->v]==0)  
                                 {               pus[p->v]=1;  
                                                 s[++dr]=p->v;   
                                                 if(s[dr]>s[st]) d[s[dr]]=d[s[st]]+p->dist;  
                                                   else       d[s[dr]]=d[s[st]]-p->dist;
                                 }  
                                 p=p->next;  
                   }  
                   st++;  
      }  
 }  
    
 int main()  
 {   citire();  
     bf(xx);  
     fout<<d[yy];  
     fin.close();  
     fout.close();  
     return 0;  
}