Cod sursa(job #3371892)

Utilizator zamhoriaHoria Zamfir zamhoria Data 1 noiembrie 2026 16:25:02
Problema Sate Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream cin("sate.in");
ofstream cout("sate.out");

const long long INF = -1e15;

int n, m, src, dest;
vector<vector<pair<int, long long>>> sate;
vector<bool> vis;

int main() {
    cin >> n >> m >> src >> dest;

    sate.resize(n + 1);
    vis.assign(n + 1, false);

    vector<long long> pos(n + 1, INF);
    queue<int> q;

    for (int i = 1; i <= m; i++) {
        int n1, n2;
        long long pondere;

        cin >> n1 >> n2 >> pondere;

        sate[n1].push_back({n2, pondere});
        sate[n2].push_back({n1, pondere});
    }

    pos[src] = 0;
    q.push(src);

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

        for (auto vecin : sate[u]) {
            int v = vecin.first;
            long long d = vecin.second;

            // daca distanta vecinului nu a fost inca calculata
            // aceasta conditie ne asigura ca nu vom revizita noduri
            // deja calculate
            if (pos[v] == INF) {
                if (u < v) // v e la dreapta lui u pe axa
                    pos[v] = pos[u] + d;
                else // v e la stanga lui u pe axa
                    pos[v] = pos[u] - d;

                q.push(v);
            }

        }
    }

    if (pos[src] == INF || pos[dest] == INF)
        cout << "Nu exista"; // nu a fost calculata pozitia fie pentru sursa, fie pentru destinatie
    else
        cout << abs(pos[dest] - pos[src]);

    return 0;
}