Cod sursa(job #3374301)

Utilizator petrica.chitacuChitacu Petrica petrica.chitacu Data 8 noiembrie 2026 22:22:24
Problema Sate Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstdlib>
using namespace std;

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

int main() {
    int N, M, X, Y;
    fin >> N >> M >> X >> Y;

    // g lista de adiacenta
    vector<vector<pair<int,int>>> g(N + 1);

    // citim cele M relatii
    for (int k = 0; k < M; k++) {
        int i, j, D;
        fin >> i >> j >> D;

        g[i].push_back({j,  D});
        g[j].push_back({i, -D});
        // muchia e retinuta in ambele sensuri, ca sa putem parcurge graful din orice sat
    }

    vector<long long> dist(N + 1, 0);

    vector<bool> viz(N + 1, false);

    queue<int> q;
    q.push(X);
    viz[X] = true;

    while (!q.empty()) {
        int u = q.front();   // luam urmatorul sat din coada
        q.pop();

        // parcurgem toti vecinii lui u
        for (auto [v, d] : g[u]) {
            if (!viz[v]) {
                viz[v] = true;
                dist[v] = dist[u] + d;
                q.push(v);
            }
        }
    }

    fout << llabs(dist[Y]) << "\n";
    return 0;
}