Cod sursa(job #2018809)

Utilizator gabriel.bjgGabriel b. gabriel.bjg Data 5 septembrie 2017 23:30:12
Problema Sate Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
//#include "stdafx.h"
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <fstream>

using namespace std;

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

typedef struct _NODE
{
	map<int, int> neighbours;
	bool visited = false;
	int cost = 0;
}NODE, *PNODE;

NODE G[30005];

int main()
{
	int n, m, x, y, i, a, b, d;
	queue<int> Q;

	fin >> n >> m >> x >> y;
	for (i = 0; i < m; ++i)
	{
		fin >> a >> b >> d;
		G[a].neighbours.insert(pair<int, int>(b, d));
		G[b].neighbours.insert(pair<int, int>(a, d));
	}

	Q.push(x);
	G[x].visited = true;
	while (!Q.empty())
	{
		a = Q.front();
		for (pair<int, int> neighbour : G[a].neighbours)
		{
			if (G[neighbour.first].visited)
				continue;
			if (neighbour.first > a)
			{
				G[neighbour.first].cost += neighbour.second;
			}
			else
			{
				G[neighbour.first].cost -= neighbour.second;
			}
			G[neighbour.first].visited = true;
			Q.push(neighbour.first);
		}
		Q.pop();
	}

	fout << G[y].cost << "\n";

	return 0;
}