Cod sursa(job #181924)

Utilizator alexeiIacob Radu alexei Data 20 aprilie 2008 00:46:53
Problema Sate Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include<stdio.h>
#define nmax 300500
#define nn 30033


int m[nmax];
int d[nn],gr[nn];
int *a[nn],*a2[nn];
long long solfin;
int n,M,x,y;

void solve(int nod,int solfin)
{
int aux=a[nod][0]; 
    
    
    if( aux ){ 
     if( nod<=y )
     solfin+=a[nod][aux]; 
     else
     solfin-=a[nod][aux];
     printf("%d\n",solfin);
     return;
    }
    else
    {
        int i;
        
        for(i=1; i<=gr[nod]; ++i)
        {aux=a2[nod][i];
                 if( aux!=0 )
                       if( aux>nod ){
                       a2[nod][i]=0;
                       solve(aux,solfin+a[nod][i]);}
                       else{
                       a2[nod][i]=0;
                       solve(aux,solfin-a[nod][i]);
                       }
        }
    }

}
int main()
{
    freopen("sate.in","r",stdin);
    freopen("sate.out","w",stdout);
    
    
    scanf("%d%d%d%d",&n,&M,&x,&y);

int aux1,aux2,aux3,i,aux4,aux5;
int j=0;
    
    for(i=1; i<=M; ++i)
    {
    scanf("%d%d%d",&aux1,&aux2,&aux3);
    
    m[++j]=aux1;
    m[++j]=aux2;
    m[++j]=aux3;
    ++gr[aux1];
    ++gr[aux2];
    }
    
    for(i=1; i<=n; ++i){
    a[i]=new int[gr[i]];
    a2[i]=new int[gr[i]];
    a[i][0]=0;
    a2[i][0]=0;      
    gr[i]=0;
    }
    
    for(i=1; i<=j; i+=3){
    
    aux1=m[i];
    aux2=m[i+1];
    aux3=m[i+2];
    ++gr[aux1];
    ++gr[aux2];
    aux4=gr[aux1];
    aux5=gr[aux2];
    
    
     a[ aux1 ][ aux4 ]=aux3;
    a2[ aux1 ][ aux4 ]=aux2;
    
     a[ aux2 ][ aux5 ]=aux3;
    a2[ aux2 ][ aux5 ]=aux1;
    
    if( aux2==y )
    a[ aux1 ][ 0 ]=aux4;
    if( aux1==y )
    a[ aux2 ][ 0 ]=aux5; 
    
    }
    
    solve(x,0);
    
    
    return 0;
}