Cod sursa(job #169627)

Utilizator crawlerPuni Andrei Paul crawler Data 1 aprilie 2008 20:31:52
Problema PScNv Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <cstdio>
#include <vector>
#include <bitset>
#include <cstdlib>
#include <algorithm>


using namespace std;

#define Nmax 250006
#define Mmax 1000000


struct { int nod, cost; short next; } l[Nmax+Mmax];

bitset <Nmax> v;

int n,m,K,x,y,last=Nmax,q[Nmax];

#define Dim 10000
int poz=0;
char buf[Dim];

void ins(int A,int B,short C)
{
     l[q[A]].nod = B;
     l[q[A]].cost = C;
     l[q[A]].next = ++last;
     q[A] = last;          
}

inline int cit()
{
       int ret=0;
       while (buf[poz] < 48) if (++poz == Dim) fread(buf,1,Dim,stdin), poz=0;
       while (buf[poz] > 47) 
       {
             ret = ret*10+buf[poz]-48;
             if (++poz == Dim) fread(buf,1,Dim,stdin), poz=0;
       }       
       return ret;
}

void DF(int nod)
{    
     v[nod] = 1;
     for (int i=nod;i!=0;i=l[i].next)
     {
          if (v[y] == 1) return;
          if (v[l[i].nod] == 0 && l[i].cost <= K) DF(l[i].nod);     
     }     
}

int main()
{
    freopen("pscnv.in","r",stdin);
    freopen("pscnv.out","w",stdout);

    int A,B;short C;

    fread(buf,1,Dim,stdin); poz=0;
       
    n = cit(); m = cit(); y = cit(); x = cit();
   
    for (int i=1;i<=n;++i) q[i] = i;  
   
    for (int i=1;i<=m;++i)
    {
        A = cit(); B = cit(); C = cit();
        ins(A,B,C);
        ins(B,A,C);
    }    
    
    int poz=1;
        
    #define Q(XXX) K+=XXX; v=0; DF(x);  if (!v[y]) poz+=XXX; else K-= XXX;
//    Q(512) Q(256) Q(128) Q(64) Q(32) Q(16) Q(8) Q(4) Q(2) Q(1)  
        
    printf("%d\n", poz);
    
    return 0;    
}