Cod sursa(job #197589)

Utilizator gcosminGheorghe Cosmin gcosmin Data 5 iulie 2008 11:22:29
Problema Reconst Scor 100
Compilator cpp Status done
Runda Junior Challenge 2008 Marime 1.11 kb
#include <stdio.h>
#include <vector>
using namespace std;

#define NMAX 2010
#define MP make_pair
#define ff first
#define ss second

int N, M;

vector <pair<int, int> > leg[NMAX];

char viz[NMAX];
int s[NMAX];
int coada[NMAX];

int a[NMAX];

void baga_bf(int beg)
{
	int p = 0, q = 0, x, y, c;
	coada[0] = beg;
	viz[beg] = 1;
	
	while (p <= q) {
		x = coada[p++];
		
		for (vector <pair<int, int> > :: iterator it = leg[x].begin(); it != leg[x].end(); ++it) {
			y = it->ff; c = it->ss;
			if (viz[y]) continue;
			
			s[y] = s[x] + c;
			viz[y] = 1;
			coada[++q] = y;
		}
	}
}

int main()
{
	int i, x, y, c;
	
	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, &c);
		
		x--;
		
		leg[x].push_back(MP(y, c));
		leg[y].push_back(MP(x, -c));
	}	
	
	for (i = 0; i <= N; i++) {
		if (viz[i]) continue;
		
		s[i] = 0;
		baga_bf(i);
	}
	
	for (i = 1; i <= N; i++) a[i] = s[i] - s[i - 1];
	
	for (i = 1; i <= N; i++) printf("%d ", a[i]);
	printf("\n");
	
return 0;
}