Pagini recente » Cod sursa (job #1610467) | Cod sursa (job #1164736) | Cod sursa (job #1531883) | Cod sursa (job #2323418) | Cod sursa (job #197589)
Cod sursa(job #197589)
#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;
}