Cod sursa(job #3373734)

Utilizator bl1ndIustin Petrea bl1nd Data 7 noiembrie 2026 19:00:08
Problema Sate Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

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

struct Muchie {
    int vecin;
    int distanta;
};

const int MAXN = 30005;

vector<Muchie> adj[MAXN];
int pos[MAXN];
bool vizitat[MAXN];

void bfs(int start) {
    queue<int> q;
    
    q.push(start);
    vizitat[start] = true;
    pos[start] = 0;

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

        for (const auto& edge : adj[u]) {
            int v = edge.vecin;
            int d = edge.distanta;

            if (!vizitat[v]) {
                vizitat[v] = true;
                pos[v] = pos[u] + d;
                q.push(v);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);

    int N, M, X, Y;
    if (!(fin >> N >> M >> X >> Y)) return 0;

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

    bfs(X);

    fout << abs(pos[Y] - pos[X]) << "\n";

    return 0;
}