Cod sursa(job #729787)

Utilizator danalex97Dan H Alexandru danalex97 Data 30 martie 2012 08:12:05
Problema Sate Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#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;
}