Cod sursa(job #1739365)

Utilizator LucianTLucian Trepteanu LucianT Data 9 august 2016 12:53:17
Problema Reconst Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <bits/stdc++.h>
#define maxN 2004
using namespace std;
int n,m,i,j,x,y,z;
vector<pair<int,int> >v[maxN];
int sum[maxN];
bool seen[maxN];
void dfs(int nod)
{
    seen[nod]=true;
    for(vector<pair<int,int> >::iterator it=v[nod].begin();it!=v[nod].end();it++)
        if(!seen[it->first])
            sum[it->first]=sum[nod]+(it->second),
            dfs(it->first);
}
int main()
{
    freopen("reconst.in","r",stdin);
    freopen("reconst.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++)
        scanf("%d %d %d",&x,&y,&z),
        v[x-1].push_back(make_pair(y,z)),
        v[y].push_back(make_pair(x-1,-z));
    for(i=1;i<=n;i++)
        if(!seen[i])
            dfs(i);
    for(i=1;i<=n;i++)
        printf("%d ",sum[i]-sum[i-1]);
    return 0;
}