Cod sursa(job #2965282)

Utilizator apocal1ps13Stefan Oprea Antoniu apocal1ps13 Data 14 ianuarie 2023 19:26:01
Problema Sate Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<iostream>
#include<vector>
#include<fstream>
#include<queue>
std::ifstream in("sate.in");
std::ofstream out("sate.in");
using namespace std;
int n, m, u, v, cost;
int x, y;
vector<pair<int, int>>g[30001];
vector<int>dp, viz;
queue<int>coada;
int main() {
	in >> n >> m >> x >> y;
	dp = viz = vector<int>(n + 1);
	while (m--) {
		in >> u >> v >> cost;
		g[u].push_back(make_pair(v, cost));
		g[v].push_back(make_pair(u, cost));
	}
	coada.push(x);
	viz[x] = 1;
	while (!coada.empty()) {
		int node = coada.front();
		coada.pop();
		for (auto i : g[node]) {
			int next = i.first;
			int cost = i.second;
			if (next > node) dp[next] = dp[node] + cost;
			else dp[next] = dp[node] - cost;
			if (!viz[next]) coada.push(next), viz[next] = 1;
		}
	}
	out << dp[y];
	return 0;
}