Cod sursa(job #735067)

Utilizator robertpoeRobert Poenaru robertpoe Data 15 aprilie 2012 17:13:30
Problema Sate Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include<fstream>
#include<vector>
#define PP pair
#define MP make_pair
#define dim 30001
using namespace std;
ifstream f("sate.in");
ofstream g("sate.out");
short ARB[dim];
short G[dim];
int n,m,x,y;
int i,x2,y2,c;
vector<PP<int,int> >A[dim];
typedef vector<PP<int, int> >::iterator it;
void dfs(int X)
{	
	for(it i=A[X].begin();i<A[X].end();++i)
	{	
		if(G[i->first]) 
			continue;
		ARB[i->first]=ARB[X]+i->second;
		G[i->first]=1;
		dfs(i->first);
	}
}
int main()
{	
	f>>n>>m>>x>>y;
	for(;m;--m)
		f>>x2>>y2>>c,A[x2].push_back(MP(y2, c)),A[y2].push_back(MP(x2, -c));
	G[1]=1;
	dfs(x);
	int rez=ARB[y]-ARB[x];
	g<<rez;
	return 0;
}