Pagini recente » Cod sursa (job #77634) | Cod sursa (job #2652316) | Cod sursa (job #1969142) | Cod sursa (job #599483) | Cod sursa (job #729787)
Cod sursa(job #729787)
#include <fstream>
#include <algorithm>
using namespace std;
#define min(a ,b) ( ( a<b ) ? a : b )
#define max(a ,b) ( ( a>b ) ? a : b )
#define abs(x) ( ( x>0 ) ? x : -x )
ifstream F("sate.in");
ofstream G("sate.out");
#define Nmax 30011
#define Mmax 200066
struct Task{ int b;int e;int l; };
int N,M,X,Y;
bool Rez[Nmax];
int D[Nmax];
Task T[Mmax];
int Start[Nmax],End[Nmax];
int pozitionare(int st,int dr)
{
int xst,xdr;
xst=0;
xdr=-1;
while (st<dr)
if (T[st].b<T[dr].b)
{
st+=xst;
dr+=xdr;
}
else
{
swap(T[st].b,T[dr].b);
swap(T[st].e,T[dr].e);
swap(T[st].l,T[dr].l);
xst=1-xst;
xdr=-1-xdr;
st+=xst;
dr+=xdr;
}
return st;
}
void quick(int st,int dr)
{
int p=pozitionare(st,dr);
if (st<p-1)
quick(st,p-1);
if (p+1<dr)
quick(p+1,dr);
}
void read()
{
F>>N>>M>>X>>Y;
int M2=0;
for (int i=1;i<=M;++i)
{
F>>T[++M2].b>>T[M2].e>>T[M2].l;
T[++M2].b=T[M2-1].e;
T[M2].e=T[M2-1].b;
T[M2].l=T[M2-1].l;
}
M=M2;
quick(1,M);
for (int i=1;i<=M;++i)
{
if ( ! Start[T[i].b] )
Start[T[i].b]=i;
End[T[i].b]=i;
}
}
void Apel(int s,int e)
{
Rez[ T[s].b ]=true;
while ( !Rez[Y] )
for (int i=s;i<=e;++i)
if ( !Rez[ T[i].e ] )
{
D[ T[i].e ]= ( T[i].e > T[i].b ) ? D[ T[i].b ] + T[i].l : D[ T[i].b ] - T[i].l ;
Apel( Start[ T[i].e ], End[ T[i].e ] );
}
}
int main()
{
read();
Apel(Start[X],End[X]);
G<<abs(D[Y])<<'\n';
F.close();
G.close();
return 0;
}