Cod sursa(job #2544568)

Utilizator CosminMorarMorar Cosmin Andrei CosminMorar Data 12 februarie 2020 11:26:01
Problema Sate Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 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, searched;

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 search(int i, bool& found) {
    if (found)
        return;
    for (pair<int, int> way : nod[i])
        if (!searched[way.first]) {
            searched[way.first] = true;
            if (way.first == x || way.first == y) {
                found = true;
                return;
            }
            search(way.first, found);
        }
}

int findLeftNode() {
    for (int i = 1; i <= n; i++)
        if (!searched[i]) {
            bool found = false;
            searched[i] = true;
            search(i, found);
            if (found)
                return i;
        }
}

void genDistance() {
    int leftNode = findLeftNode();
    stack<int> s;
    s.push(leftNode);

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

        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;
}