Cod sursa(job #2543355)

Utilizator CosminMorarMorar Cosmin Andrei CosminMorar Data 11 februarie 2020 08:33:02
Problema Sate Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 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 genDistances() {
    for (int i = 1; i <= n; i++)
        if (!haveDist[i] && nod[i].size() && (!haveDist[x] || !haveDist[y])) {
            stack<int> s;
            s.push(i);

            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();
    genDistances();
    fout << dist[y] - dist[x];
    return 0;
}