Cod sursa(job #3170276)

Utilizator zetef3Dediu Stefan zetef3 Data 17 noiembrie 2023 10:01:50
Problema Sate Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <iostream>
#include <fstream>
#include <utility>
#include <algorithm>
#include <vector>

#define NMAX 30002

using namespace std;

ifstream f("sate.in");
ofstream g("sate.out");

int N,M,X,Y;
vector<int> d;
vector<pair<int,int>> m[NMAX];

void read() {
    f >> N >> M >> X >> Y;
    X--;Y--;

    d.resize(N);

    for (int i=0;i<M;i++) {
        int u,v,c;
        f >> u >> v >> c;
        u--;v--;

        m[u].push_back(make_pair(v,c));
        m[v].push_back(make_pair(u,-c));
    }

    fill(d.begin(), d.end(), -1);
}

void dfs(int u, int D) {
    d[u]=D;
    for (auto v:m[u]) {
        if (d[v.first] == -1) {
            dfs(v.first, D+v.second);
        }
    }
}

int main()
{
    read();
    dfs(X,0);
    g << d[Y];
    return 0;
}