Cod sursa(job #3372052)

Utilizator prares06Papacioc Rares-Ioan prares06 Data 2 noiembrie 2026 14:13:14
Problema Sate Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define ll long long

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

int n, m, x, y;
vector<ll> p, viz;
vector<vector<pii>> G;

int main() {
    fin >> n >> m >> x >> y;

    p.resize(n + 1);
    viz.resize(n + 1);
    G.resize(n + 1);

    for(int a, b, c; m--;) {
        fin >> a >> b >> c;
        G[a].push_back({b, c});
        G[b].push_back({a, -c});
    }

    queue<int> q;
    viz[x] = 1;
    q.push(x);

    while(!q.empty()) {
        int node = q.front();
        q.pop();

        if(node == y) {
            break;
        }

        for(auto [x, c] : G[node]) {
            if(!viz[x]) {
                viz[x] = true;
                p[x] = p[node] + c;
                q.push(x);
            }
        }
    }

    fout << (p[y] > 0 ? p[y] : -p[y]);
}