Cod sursa(job #2544952)

Utilizator CosminMorarMorar Cosmin Andrei CosminMorar Data 12 februarie 2020 18:31:34
Problema Sate Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
using namespace std;
ifstream fin("sate.in");
ofstream fout("sate.out");
int n, m, x, y;
vector<pair<int, int> > nod[30001];
int dist[30001];
bitset<30001> haveDist;

void readAndSet() {
    fin >> n >> m >> x >> y;
    for (int i = 1; i <= m; i++) {
        int a, b, cost;
        fin >> a >> b >> cost;
        nod[a].push_back(make_pair(b, cost));
        nod[b].push_back(make_pair(a, -cost));
    }
}

void genDistance() {
    stack<int> s;
    s.push(x);
    haveDist[x] = true;

    while (!s.empty()) {
        int i = s.top();
        s.pop();

        if (haveDist[y])
            break;

        for (pair<int, int> way : nod[i])
            if (!haveDist[way.first]) {
                haveDist[way.first] = true;
                dist[way.first] = dist[i] + way.second;
                s.push(way.first);
            }
    }
}

int main() {
    readAndSet();
    genDistance();
    fout << dist[y] - dist[x];
    return 0;
}