Cod sursa(job #1988342)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 2 iunie 2017 19:01:13
Problema Reconst Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin ("reconst.in"); ofstream fout ("reconst.out");

const int nmax = 2000 + 5;

bool viz[nmax + 1];

vector<pair<int, int>> g[nmax + 1];
int s[nmax + 1];

void dfs (int nod) {
    viz[ nod ] = 1;

    for (auto i : g[ nod ]) {
        if (viz[ i.first ] == 0) {
            s[ i.first ] = s[ nod ] + i.second;

            dfs(i.first);
        }
    }
}

int main() {
    int n, m;
    fin >> n >> m;

    for (int i = 0; i < m; ++ i) {
        int a, b, x;
        fin >> a >> b >> x;

        g[a - 1].push_back(make_pair(b, x));
        g[ b ].push_back(make_pair(a - 1, -x));
    }

    for (int i = 0; i <= n; ++ i) {
        if (viz[ i ] == 0) {
            s[ i ] = 0;
            dfs( i );
        }
    }

    for (int i = 1; i <= n; ++ i) {
        fout << s[ i ] - s[i - 1] << " ";
    }
    fout << "\n";

    fin.close();
    fout.close();
    return 0;
}