4   4   -- 4 вершины, 4 ребра
 450   379   230   520   -- веса вершин (нумерация вершин с 1) 
 3   4   -- ребра (из №3 можно попасть в №4)
 2   4   --
 2   3   --
 2   4   --

Oтвет:
 450   1129   750   520 

Ограничения:
число_вершин <=  20000 
число_ребер <=  500000 

#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <bitset>
using namespace std;

int read_ui() {
    int n =  0 ;
    char c;
    while (!isdigit(c = getchar()));
    while (isdigit(c)) {
        n = n *  10  + (c - '0');
        c = getchar();
    }
    return n;
}

int tcs, nv, ne, u, v;
bool b[ 20005 ];
int w[ 20005 ];
int t[ 20005 ];
vector<int> d[ 500005 ];
bitset< 20005 > z[ 20005 ];
bitset< 20005 > c[ 20005 ];
bitset< 20005 > o;

int main() {
    freopen("E:\\C++\\SPOJ\\TestData\\88.txt", "rt", stdin);
    freopen("E:\\C++\\SPOJ\\TestData\\99.txt", "wt", stdout);
    o.reset();
    tcs = read_ui();            -------- // число тест-кейсов (в каждом тест-кейсе свой, новый граф)
    while (tcs-- > 0) {
        nv = read_ui();
        ne = read_ui();
        for (int i =  1 ; i <= nv; ++i) t[i] =  0 ;
        for (int i =  1 ; i <= nv; ++i) {
            w[i] = read_ui();
            b[i] = false;
            c[i].reset();
            d[i].clear();
            z[i].reset();
            z[i].flip(i);
        }

        for (int i =  1 ; i <= ne; ++i) {
            u = read_ui();
            v = read_ui();
            if (!c[u].test(v)) {
                c[u].flip(v);
                d[v].push_back(u);
            }
        }

        int sch =  0 ;

        while (sch < nv) {
            for (int i =  1 ; i <= nv; ++i) {
                if (!b[i] && c[i] == o) {
                    b[i] = true;
                    for (int j =  0 ; j < (int)d[i].size(); ++j) {

                        z[d[i][j]] = z[d[i][j]] |= z[i];

                        c[d[i][j]].flip(i);

                    }

                    ++sch;
                }
            }
        }

        for (int i =  1 ; i <= nv; ++i)
            for (int k =  1 ; k <= nv; ++k) if (z[i].test(k))
                t[i] += w[k];

        for (int i =  1 ; i < nv; ++i) printf("%d ", t[i]);
        printf("%d\n", t[nv]);

    }

return  0 ;
}

--Input:

 2   --число тест-кейсов

 4   3 
 510   713   383   990 
 4   1 
 4   2 
 2   1 

 6   4 
 450   379   230   520   6   7 
 3   4 
 2   4 
 2   3 
 2   4 


--Ответ:

 510   1223   383   2213 
 450   1129   750   520   6   7 

#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <bitset>
using namespace std;

const int n =  20000 ;
const int m =  500000 ;
int tcs =  1 ;
bitset<n +  1 > a[n +  1 ];

int randint(int lt, int rt) {
    return lt + (int)((rt - lt) * (double)rand() / RAND_MAX + 1E- 15 );
}

int main() {
    freopen("E:\\4882in.txt", "wt", stdout);
    printf("%d\n", tcs);
    while (tcs-- > 0) {
        printf("%d %d\n", n, m);
        for (int i =  1 ; i < n; ++i) printf("%d ", randint( 1 ,  1000 ));
        printf("%d\n", randint( 1 ,  1000 ));
        for (int i =  1 ; i <= n; ++i) {
            a[i].reset();
            a[i].flip(i);
        }
        int cnt =  0 ;
        while (cnt < m) {
            int i = randint( 1 , n);
            int j = randint( 1 , n);
            if (!a[i].test(j)) {
                a[j] = a[j] |= a[i];
                printf("%d %d\n", i, j);
                ++cnt;
            }
        }
    }

return  0 ;
} 

#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <bitset>
using namespace std;

int read_ui() {
    int n =  0 ;
    char c;
    while (!isdigit(c = getchar()));
    while (isdigit(c)) {
        n = n *  10  + (c - '0');
        c = getchar();
    }
    return n;
}

const int nmx =  20001 ;

int tcs, nv, ne, u, v, sch;
int w[nmx];
int t[nmx];
int b[nmx];
vector<int> p;
vector<int> d[nmx];
bitset<nmx> z[nmx];
bitset<nmx> c[nmx];


int main() {
    freopen("E:\\C++\\SPOJ\\TestData\\4882in2.txt", "rt", stdin);
    freopen("E:\\C++\\SPOJ\\TestData\\4882out.txt", "wt", stdout);
    tcs = read_ui();
    while (tcs-- > 0) {
        nv = read_ui();
        ne = read_ui();
        for (int i =  1 ; i <= nv; ++i) {
            w[i] = read_ui();
            t[i] =  0 ;
            b[i] =  0 ;
            c[i].reset();
            d[i].clear();
            z[i].reset();
            z[i].set(i);
        }

        for (int i =  1 ; i <= ne; ++i) {
            u = read_ui();
            v = read_ui();
            if (!c[u].test(v)) {
                ++b[u];
                c[u].set(v);
                d[v].push_back(u);
            }
        }


        sch =  0 ;
        p.clear();
        for (int i =  1 ; i <= nv; ++i)
            if (b[i] ==  0 ) {p.push_back(i); b[i] = - 1 ;}
        sch += (int)p.size();


        while (!p.empty()) {
            for (int i =  0 ; i < (int)p.size(); ++i) {
                v = p[i];
                for (int j =  0 ; j < (int)d[v].size(); ++j) {
                    z[d[v][j]] |= z[v];
                    --b[d[v][j]];
                }
            }

            p.clear();
            for (int i =  1 ; i <= nv; ++i)
                if (b[i] ==  0 ) {p.push_back(i); b[i] = - 1 ;}
            sch += (int)p.size();
        }


        //output:
        for (int i =  1 ; i <= nv; ++i)
            for (int k =  1 ; k <= nv; ++k) if (z[i].test(k))
                t[i] += w[k];
        for (int i =  1 ; i < nv; ++i) printf("%d ", t[i]);
        printf("%d\n", t[nv]);

        printf("sch = %d\n", sch);

    }

return  0 ;
} 

 1 
 50   150 
 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1 
 1   28 
 10   40 
 29   24 
 18   44 
 41   37 
 9   43 
 35   26 
 15   1 
 5   18 
 8   9 
 49   22 
 6   1 
 1   19 
 27   28 
 9   33 
 23   18 
 3   30 
 39   40 
 26   15 
 43   36 
 47   46 
 27   7 
 23   12 
 43   11 
 39   42 
 30   20 
 14   15 
 42   2 
 19   5 
 34   3 
 1   46 
 29   34 
 42   36 
 24   11 
 37   23 
 23   47 
 37   6 
 30   19 
 37   30 
 29   18 
 8   12 
 21   40 
 26   49 
 37   17 
 9   33 
 25   4 
 35   25 
 8   47 
 7   45 
 34   15 
 21   4 
 48   34 
 8   43 
 41   29 
 10   9 
 41   24 
 8   25 
 36   20 
 14   28 
 34   38 
 36   24 
 7   19 
 41   2 
 26   33 
 21   6 
 47   46 
 27   17 
 24   19 
 42   16 
 23   14 
 49   15 
 37   28 
 10   38 
 42   20 
 25   44 
 2   49 
 29   3 
 27   10 
 42   31 
 33   10 
 42   7 
 16   47 
 15   17 
 7   36 
 41   35 
 13   8 
 1   3 
 40   42 
 11   6 
 6   23 
 37   34 
 27   4 
 22   10 
 35   15 
 22   12 
 29   27 
 31   8 
 25   48 
 35   46 
 10   17 
 9   49 
 23   49 
 5   31 
 5   22 
 46   3 
 44   15 
 12   38 
 21   10 
 31   30 
 30   32 
 42   41 
 31   36 
 28   19 
 10   37 
 28   45 
 12   10 
 30   35 
 29   18 
 25   4 
 37   30 
 31   34 
 40   8 
 29   43 
 45   31 
 36   3 
 33   48 
 16   28 
 15   9 
 42   37 
 8   17 
 27   22 
 21   15 
 23   25 
 8   16 
 37   16 
 41   47 
 43   36 
 15   47 
 7   4 
 39   26 
 30   47 
 4   43 
 33   16 
 6   25 
 12   15 
 46   28 
 33   6 
 25   19 
 25   39 
 25   19 

 1   1   1   1   1   1   1   2   1   3   1   2   1   1   2   1   1   1   1   1   1   1   1   1   1   1   2   1   1   3   1   1   1   2   1   2   2   1   1   1   1   2   1   1   1   1   1   1   1   1 
sch =  5 

 13   16   9   1   4   21   24   24   20   27   22   2   24   15   15   14   1   2   5   1   29   3   21   23   20   16   28   7   29   8   25   1   15   17   21   23   21   1   29   28   30   28   9   1   1   12   13   18   15   1 

 15   19   11   1   6   26   30   34   33   41   27   2   35   18   17   16   1   2   7   1   42   3   25   28   21   22   42   9   43   10   35   1   17   18   27   29   26   1   42   40   46   39   30   1   1   14   15   19   18   1 

import networkx as nx

a = open('E:\\C++\\SPOJ\\TestData\\4882in3.txt', 'rt').readlines()
a = a[ 3 :]
a = [tuple(map(int, ai.split())) for ai in a]

g = nx.DiGraph()
g.add_edges_from(a)

print nx.is_directed_acyclic_graph(g)


>>> 
True
>>> 

 41   467   334   500  ... ... ...
sch =  0 
Time =  26 . 11 

sch =  20000 
Time =  5 . 45 
 8467951   7916848   8095741   8352873   8309569  .......
Time =  33 . 42 

//============================================================================
// Name        : DAGCNT2.cpp
// Author      : Shaka
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#define MAXN  20000 
using namespace std;

typedef set<int> si;
typedef si::iterator sii;

si links[MAXN+ 1 ];
si vis[MAXN+ 1 ];
int w[MAXN+ 1 ];
bool incoming[MAXN+ 1 ], flag[MAXN+ 1 ];

void dfs(int v) {
   vis[v].insert(v);
   flag[v] =  1 ;
   for (sii i = links[v].begin(); i!=links[v].end(); i++) {
      int j = *i;
      if (!flag[j])
         dfs(j);
      for (sii p = vis[j].begin(); p!=vis[j].end(); p++)
         vis[v].insert(*p);
   }
}

int main() {
   freopen("E:\\C++\\SPOJ\\TestData\\4882in1.txt", "rt", stdin);
   freopen("E:\\C++\\SPOJ\\TestData\\999.txt", "wt", stdout);
   register int cas, N, M, i, j, s;
   scanf("%d", &cas);
   while (cas--) {
      scanf("%d %d", &N, &M);
      for (i =  1 ; i <= N; i++) {
         scanf("%d", w+i);
         links[i].clear();
         vis[i].clear();
      }
      memset(incoming, false, N+ 1 );
      while (M--) {
         scanf("%d %d", &i, &j);
         if (i!=j) {
            links[i].insert(j);
            incoming[j] =  1 ;
         }
      }
      memset(flag, false, N+ 1 );
      for (i =  1 ; i <= N; i++)
         if (!incoming[i])
            dfs(i);
      for (i =  1 ; i <= N; i++) {
         s =  0 ;
         for (sii k = vis[i].begin(); k != vis[i].end(); k++)
            s+=w[*k];
         printf("%d%c", s, i==N ? '\n' : ' ');
      }
   }
   return  0 ;
}

/*
Как сабжевый бонус, код для определения
является ли данный ориентированный граф графом без циклов:
is_directed_acyclic_graph

Формат входного файла:
nv ne      <- число вершин (нумерация с 1) и число ор. ребер;
v1 v2      <- список "ne" штук ребер;
... ...
... ...
vN vM
*/

#include <ctime>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <bitset>
using namespace std;

#define NMX  20000       //-- макс. число вершин в графе;

int nv, ne, u, v, sch;
int b[NMX+ 1 ];
vector<int> p, q;
vector<int> d[NMX+ 1 ];
bitset<NMX+ 1 > c[NMX+ 1 ];


int main() {
    #define fp stdin
    //FILE* fp = fopen("E:\\C++\\SPOJ\\TestData\\is_dag_in.txt", "rt");

    clock_t begin = clock();
    fscanf(fp, "%d %d", &nv, &ne);

    for (int i =  1 ; i <= nv; ++i) {
        b[i] =  0 ;
        c[i].reset();
        d[i].clear();
    }

    for (int i =  1 ; i <= ne; ++i) {
        fscanf(fp, "%d %d", &u, &v);
        if (u == v) continue;
        if (!c[u].test(v)) {
            ++b[u];
            c[u].set(v);
            d[v].push_back(u);
        }
    }
    //fclose(fp);

    sch =  0 ;
    p.clear();
    for (int i =  1 ; i <= nv; ++i)
        if (b[i] ==  0 ) p.push_back(i);
    sch += (int)p.size();

    while (!p.empty()) {
        q.clear();
        for (int i =  0 ; i < (int)p.size(); ++i) {
            v = p[i];
            for (int j =  0 ; j < (int)d[v].size(); ++j) {
                --b[d[v][j]];
                if (b[d[v][j]] ==  0 ) q.push_back(d[v][j]);
            }
        }
        p.swap(q);
        sch += (int)p.size();
    }

    if (sch == nv) printf("YES, no cycles in the graph\n");
    else printf("NO, the graph has cycles\n");
    printf("Time = %.2f(s)\n", (double)(clock() - begin) / CLOCKS_PER_SEC);

    system("pause");
return  0 ;
} 

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;

#define NMX  222 

int nv, ne;
int b[NMX];
vector<int> a[NMX];


void foo(int cur, int prev) {
    if (b[cur] ==  0 ) {
        b[cur] = prev;
        for (int i =  0 ; i < (int)a[cur].size(); ++i)
            if (a[cur][i] != prev)
                foo(a[cur][i], cur);
    }
    else {
        printf("%d ", cur);
        int j = prev;
        while (j != cur) {
            printf("%d ", j);
            j = b[j];
        }
        printf("\n");
    }
}


int main() {
    freopen("E:\\88.txt", "rt", stdin);
    freopen("E:\\99.txt", "wt", stdout);

    scanf("%d %d", &nv, &ne);

    for (int i =  1 ; i <= nv; ++i) {
        a[i].clear();
        b[i] =  0 ;
    }

    for (int i =  1 ; i <= ne; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        a[u].push_back(v);
        a[v].push_back(u);
    }

    foo( 1 ,  0 );

return  0 ;
} 

 5   7        -- 5 вершин,  7 неориентированных ребер;
 1   2 
 2   3 
 4   3 
 2   4 
 5   4 
 5   2 
 1   5 

 2   4   3  
 2   5   4   3  
 2   1   5   4   3  
 4   2   1   5  
 5   2   1  
 5   1         <<< ???         и не найден цикл ( 2 ,  4 ,  5 ) -- попозже посмотрю;

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;

#define NMX  222 

int nv, ne;
int b[NMX];
vector<int> a[NMX];


void foo(int cur, int prev) {
    if (b[cur] ==  0 ) {
        b[cur] = prev;
        for (int i =  0 ; i < (int)a[cur].size(); ++i)
            if (a[cur][i] != prev)
                foo(a[cur][i], cur);
        b[cur] =  0 ;
    }
    else {
        printf("%d ", cur);
        int j = prev;
        while (j != cur) {
            printf("%d ", j);
            j = b[j];
        }
        printf("\n");
    }
}


int main() {
    freopen("E:\\88.txt", "rt", stdin);
    freopen("E:\\99.txt", "wt", stdout);

    scanf("%d %d", &nv, &ne);

    for (int i =  1 ; i <= nv; ++i) {
        a[i].clear();
        b[i] =  0 ;
    }

    for (int i =  1 ; i <= ne; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        a[u].push_back(v);
        a[v].push_back(u);
    }

    b[ 1 ] =  1 ;
    for (int k =  0 ; k < (int)a[ 1 ].size(); ++k)
        foo(a[ 1 ][k],  1 );

return  0 ;
} 

 2   4   3  
 2   5   4   3  
 1   5   4   3   2  
 2   3   4  
 2   5   4  
 1   5   4   2  
 2   3   4   5  
 2   4   5  
 1   5   2  
 1   2   3   4   5  
 4   2   3  
 5   2   3   4  
 1   2   4   5  
 4   3   2  
 5   2   4  
 1   2   5  
 2   4   3  
 5   4   3   2  
 2   3   4  
 5   4   2  

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

#define NMX  222 

typedef vector<int> cycle;
set<cycle> sc;

int nv, ne;
int b[NMX];
vector<int> a[NMX];


void foo(int cur, int prev) {
    if (b[cur] ==  0 ) {
        b[cur] = prev;
        for (int i =  0 ; i < (int)a[cur].size(); ++i)
            if (a[cur][i] != prev)
                foo(a[cur][i], cur);
        b[cur] =  0 ;
    }
    else {
        cycle p, q;
        p.push_back(cur);
        int j = prev;
        while (j != cur) {
            p.push_back(j);
            j = b[j];
        }
        q = p;
        sort(q.begin(), q.end());
        if (sc.count(q) !=  0 )
            return;
        sc.insert(q);
        for (int j =  0 ; j < (int)p.size(); ++j)
            printf("%d ", p[j]);
        printf("\n");
    }
}


int main() {
    freopen("E:\\88.txt", "rt", stdin);
    freopen("E:\\99.txt", "wt", stdout);

    scanf("%d %d", &nv, &ne);

    for (int i =  1 ; i <= nv; ++i) {
        a[i].clear();
        b[i] =  0 ;
    }

    for (int i =  1 ; i <= ne; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        a[u].push_back(v);
        a[v].push_back(u);
    }

    b[ 1 ] =  1 ;
    for (int k =  0 ; k < (int)a[ 1 ].size(); ++k)
        foo(a[ 1 ][k],  1 );

return  0 ;
} 

 2   4   3  
 2   5   4   3  
 1   5   4   3   2  
 2   5   4  
 1   5   4   2  
 1   5   2