Cod sursa(job #735076)

Utilizator robertpoeRobert Poenaru robertpoe Data 15 aprilie 2012 17:34:55
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include<fstream>
#include<vector>
#define dim 30010
#define MP make_pair
#define PP pair
using namespace std;
ifstream f("sate.in");
ofstream g("sate.out");
int N, M, X, Y;
int ARB[dim];
bool G[dim];
vector<PP<int, int> >A[dim];
typedef vector<PP<int, int> >::iterator it;
void SOLVE(int node)
{	
	for(it i=A[node].begin();i!=A[node].end();i++)
	{	
		if(G[i->first]==1) 
			continue;
		ARB[i->first]=ARB[node]+i->second;
		G[i->first]=1;
		SOLVE(i->first);
	}
}
int main()
{	
	int i, x, y, c;
	f>>N>>M>>X>>Y;
	for(i=1;i<=M;i++)
	{	
		f>>x>>y>>c;
		A[x].push_back(MP(y, c));
		A[y].push_back(MP(x, -c));
	}
	G[1] = 1;
	SOLVE(X);
	int rez=ARB[Y]-ARB[X];
	g<<rez;
	return 0;
}