Cod sursa(job #488076)

Utilizator darrenRares Buhai darren Data 27 septembrie 2010 17:17:54
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include <vector>

using namespace std;

typedef long long i64;

void Dfs(int i);

int n, m, x, y;
vector<pair<i64, int> > v[30002];
i64 d[30002];
bool s[30002];

int main()
{
	ifstream fin("sate.in");
	ofstream fout("sate.out");

	fin >> n >> m >> x >> y;
	for (int i = 1; i <= n; ++i)
		d[i] = -1;
	d[x] = 0;
	for (int i = 1, nod1, nod2, cost; i <= m; ++i)
	{
		fin >> nod1 >> nod2 >> cost;
		v[nod1].push_back(make_pair(nod2, cost));
		v[nod2].push_back(make_pair(nod1, cost));
	}

	Dfs(x);

	fout << d[y];

	fin.close();
	fout.close();
}

void Dfs(int i)
{
	s[i] = true;
	for (vector<pair<i64, int> >::iterator it = v[i].begin(); it != v[i].end(); ++it)
		if (!s[it->first])
		{
			if (it->first < i) d[it->first] = d[i] - it->second;
			else               d[it->first] = d[i] + it->second;
			Dfs(it->first);
		}
}