Cod sursa(job #3374249)

Utilizator dcamaximDuca Maxim dcamaxim Data 8 noiembrie 2026 21:11:18
Problema Sate Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

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

    int n, m, x, y;
    fin >> n >> m >> x >> y;

    vector<vector<pair<int, int>>> vecini(n + 1);

    for (int k = 0; k < m; ++k) {
        int i, j, d;
        fin >> i >> j >> d;
        vecini[i].push_back({j, d});
        vecini[j].push_back({i, -d});
    }

    vector<int> dist(n + 1, 0);
    vector<bool> vizitat(n + 1, false);
    queue<int> coada;

    vizitat[x] = true;
    dist[x] = 0;
    coada.push(x);

    while (!coada.empty()) {
        int sat_curent = coada.front();
        coada.pop();

        if (sat_curent == y) {
            break;
        }

        for (auto legatura : vecini[sat_curent]) {
            int sat_vecin = legatura.first;
            int km = legatura.second;

            if (!vizitat[sat_vecin]) {
                vizitat[sat_vecin] = true;
                dist[sat_vecin] = dist[sat_curent] + km;
                coada.push(sat_vecin);
            }
        }
    }

    fout << abs(dist[y]) << "\n";

    return 0;
}