Cod sursa(job #2021244)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 12 septembrie 2017 22:22:45
Problema Reconst Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <bits/stdc++.h>

const int MAXN = (int) 2e3;

std::vector < std::pair <int, int> > g[MAXN + 1];

int sol[MAXN + 1];
bool viz[MAXN + 1];

void dfs(int nod) {
    viz[nod] = 1;
    for(auto it : g[nod])
       if(!viz[it.first]) {
           sol[it.first] = sol[nod] + it.second;
           dfs(it.first);
       }
}

int main() {
    FILE *fi, *fout;
    int i, n, m, l, r, val;
    fi = fopen("reconst.in" ,"r");
    fout = fopen("reconst.out" ,"w");
    fscanf(fi,"%d %d " ,&n,&m);
    for(i = 1; i <= m; i++) {
        fscanf(fi,"%d %d %d " ,&l,&r,&val);
        g[l - 1].push_back({r, val});
        g[r].push_back({l - 1, -val});
    }
    for(i = 0; i <= n; i++)
        if(!viz[i])
            dfs(i);
    for(i = 1; i <= n; i++)
        fprintf(fout,"%d " ,sol[i] - sol[i - 1]);
    fclose(fi);
    fclose(fout);
    return 0;
}