Cod sursa(job #399479)

Utilizator freak93Adrian Budau freak93 Data 20 februarie 2010 15:29:25
Problema Reconst Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

const char iname[]="reconst.in";
const char oname[]="reconst.out";
const int maxn=2005;

ifstream f(iname);
ofstream g(oname);

vector<pair<int,int> > E[maxn];

int i,j,n,s[maxn],a[maxn],x,y,been[maxn],m;

queue<int> Q;

void go(int x)
{
    Q.push(x);
    been[x]=1;
    while(!Q.empty())
    {
        x=Q.front();
        Q.pop();
        for(vector<pair<int,int> >::iterator it=E[x].begin();it!=E[x].end();++it)
            if(been[it->first]==0)
            {
                been[it->first]=1;
                Q.push(it->first);
                s[it->first]=s[x]+it->second;
            }
    }
}

int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x>>y>>j;
        E[--x].push_back(make_pair(y,j));
        E[y].push_back(make_pair(x,-j));
    }
    for(i=0;i<n;++i)
        if(been[i]==0)
        {
            s[i]=0;
            go(i);
        }

    for(i=1;i<=n;++i)
        a[i]=s[i]-s[i-1],g<<a[i]<<" ";
    g<<"\n";

    f.close();
    g.close();

    return 0;
}