Cod sursa(job #2914575)

Utilizator tomaionutIDorando tomaionut Data 20 iulie 2022 13:17:35
Problema Sate Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, m, X, Y, k;
vector <pair<int, int> > a[30005];
queue <int> Q;
int dp[30005];
bitset <30005> viz;
int main()
{
	int i, j, x, y, dist;
	fin >> n >> m >> X >> Y;
	for (i = 1; i <= m; i++)
	{
		fin >> x >> y >> dist;
		if (x > y) swap(x, y);
		a[x].push_back({ y, dist });
		a[y].push_back({ x, -dist });
	}

	Q.push(X);
	viz[X] = 1;
	while (!Q.empty())
	{
		k = Q.front();
		Q.pop();
		for (auto w: a[k])
		{
			i = w.first;
			j = w.second;
			if (viz[i] == 0)
			{
				dp[i] = dp[k] + j;
				viz[i] = 1;
				Q.push(i);
			}

			if (i == Y)
			{
				fout << dp[Y] << "\n";
				return 0;
			}
		}
	}
	fout << "-1\n";

	return 0;
}