Cod sursa(job #3269585)

Utilizator BledeaAlexBledea Alexandru BledeaAlex Data 19 ianuarie 2025 20:06:24
Problema Sate Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 3e4 + 1;
int N, M, X, Y;
int dist[N_MAX];

struct muchie
{
    int nod, cost;
};

vector<muchie> G[N_MAX];

void SetInput(string name)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    (void)!freopen((name + ".in").c_str(), "r", stdin);
    (void)!freopen((name + ".out").c_str(), "w", stdout);
}

void ReadInput()
{
    cin >> N >> M >> X >> Y;

    for(int i = 0, n1, n2, c; i < M; i++)
    {
        cin >> n1 >> n2 >> c;
        G[n1].push_back(muchie{n2, c});
        G[n2].push_back(muchie{n1, -c});
    }
}

void Solve()
{
    queue<int> Q;

    for(int i = 1; i <= N; i++)
        dist[i] = -1;
    dist[X] = 0;
    Q.push(X);

    while(not Q.empty())
    {
        int nod = Q.front();
        Q.pop();

        if(nod == Y)
            break;

        for(muchie fiu : G[nod])
            if(dist[fiu.nod] == -1)
            {
                dist[fiu.nod] = dist[nod] + fiu.cost;
                Q.push(fiu.nod);
            }
    }

    cout << dist[Y] << '\n';
}

int main()
{
    SetInput("sate");

    ReadInput();
    Solve();

    return 0;
}