Cod sursa(job #721593)

Utilizator andunhillMacarescu Sebastian andunhill Data 23 martie 2012 20:32:32
Problema Sate Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include<fstream>
#include<vector>
using namespace std;

ifstream f("sate.in");
ofstream g("sate.out");

int N, M, X, Y;
int dist[30009];
bool v[30009];

vector<pair<int, int> >graph[30009];
typedef vector<pair<int, int> >::iterator it;

void DFS(int node)
{	for(it i = graph[node].begin(); i != graph[node].end(); i++)
	{	if(v[i->first] == true) continue;
		
		dist[i->first] = dist[node] + i->second;
		v[i->first] = true;
		DFS(i->first);
	}
}

int main()
{	int i, x, y, c;
	
	f>>N>>M>>X>>Y;
	for(i = 1; i <= M; i++)
	{	f>>x>>y>>c;
		graph[x].push_back(make_pair(y, c));
		graph[y].push_back(make_pair(x, -c));
	}
	v[1] = 1;
	DFS(1);
	
	g<<dist[Y] - dist[X];
}