Cod sursa(job #283853)

Utilizator vladbBogolin Vlad vladb Data 20 martie 2009 09:28:22
Problema Sate Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 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(st>=2)
                                                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;
}