043 Boom

[•pauldb]

De ce nu generezi tu testele si sa ne ceri doar rezultatul corect? E tare neconvenabil sa ne gandim noi ce ai fi putut tu gresi si sa generam teste cu astfel de exemple.

[•assa98]

ok. Imi cer scuze. Pentru

Cod:

10 6
20 3 1 2 3
20 3 2 3 4
5 1 4
5 1 5
10 4 7 8 9 10
17 3 5 6 7

e bun:

Cod:

77
6
2
4
5
6
4
2

??

[•pauldb]

Iti da bine.

[•AlexandruValeanu]

Am si eu o nelamurire despre cum se formeaza graful. Eu am incercat sa parcurg toate nodurile de la 0->2ⁿ-1 si pentru fiecare nod aflu vecini are cam asa:

Cod:

for ( int i = 0; i < ( 1 << N ); ++i )
    {
        for ( int j = 1; j <= M; ++j )
        {
            int nod = i | sarje[j].nr;

            node x = { nod, sarje[j].P };
            G[i].push_back( x );
        }
    }

Problema este ca atunci cand fac Dijkstra de la 0 la 2ⁿ-1, pe exemplu imi da 3(de la nodul 0 folosind sarja 1 merge in 5 si din 5 folosind sarja 2 merge in 7). Am gresit modul de constructie al grafului sau imi scapa altceva...?

[•sebinechita]

Salut. Am facut problema de 100 dar am o nelamurire. Am doua surse care iau 100, una cu heapuri de mana optimizate pe biti si cealalta care foloseste priority_queue din STL. Siiii spre surprinderea mea sursa cu heapuri merge muuult mai greu decat aia cu PQ...ca sa nu mai vorbim de memorie care ii dubla. Memoria sa zicem ca o inteleg deoarece presupun ca o sa am pe teste random, relativ putine noduri in heap la un moment dat. Dar heapurile de mana nu ar trebui sa mearga mai rapid?!?