Cod sursa(job #3252232)

Utilizator luc3lexaAlexandrescu Luca luc3lexa Data 28 octombrie 2024 21:22:09
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");

const int nmax = 3e4+10;

int n,m,x,y;
vector<int> visited(nmax,0);
vector<vector<pair<int,int>>> mat(nmax);
queue<int> q;

void read_input(){
	fin >> n >> m >> x >> y;
	int nod_1,nod_2,cost;
	
	for(int i = 1;i <=m; i++){
		fin >> nod_1 >> nod_2 >> cost;
		mat[nod_1].push_back(make_pair(nod_2,cost));
		mat[nod_2].push_back(make_pair(nod_1,-cost));
	}
}

void bfs(){
	q.push(x);
	
	visited[x] = 1;
	
	while(!q.empty()){
		int nod = q.front();
		q.pop();
		for(auto nod_aux : mat[nod]){
			if(!visited[nod_aux.first]){
				visited[nod_aux.first] = visited[nod] + nod_aux.second;
				q.push(nod_aux.first);
			}
		}
	};
	
	fout << visited[y]-1;
}
int main(){
	read_input();
	bfs();
	return 0;
}