Pagini recente » Rating Muresan Alexandru (MuresanAlex26) | Cod sursa (job #493044) | Cod sursa (job #2437974) | Cod sursa (job #1382844) | Cod sursa (job #169627)
Cod sursa(job #169627)
#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;
}