Cod sursa(job #2965297)

Utilizator apocal1ps13Stefan Oprea Antoniu apocal1ps13 Data 14 ianuarie 2023 19:29:26
Problema Sate Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.1 kb
#include<iostream>
#include<vector>
#include<fstream>
#include<queue>
using namespace std;
class InParser {
private:
    FILE* fin;
    char* buff;
    int sp;

    char read_ch() {
        ++sp;
        if (sp == 4096) {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }

public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser& operator >> (int& n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        }
        else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }

    InParser& operator >> (long long& n) {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        }
        else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};
InParser in("sate.in");
std::ofstream out("sate.out");
int n, m, u, v, cost;
int x, y;
vector<pair<int, int>>g[30001];
vector<int>dp, viz;
queue<int>coada;
int main() {
    in >> n >> m >> x >> y;
    dp = viz = vector<int>(n + 1);
    while (m--) {
        in >> u >> v >> cost;
        g[u].push_back(make_pair(v, cost));
        g[v].push_back(make_pair(u, cost));
    }
    coada.push(x);
    viz[x] = 1;
    while (!coada.empty()) {
        int node = coada.front();
        coada.pop();
        for (auto i : g[node]) {
            int next = i.first;
            int cost = i.second;
            if (next > node) dp[next] = dp[node] + cost;
            else dp[next] = dp[node] - cost;
            if (!viz[next]) coada.push(next), viz[next] = 1;
        }
    }
    out << dp[y];
    return 0;
}