Poveste şi cerinţă...
Se da un graf orientat cu N noduri. Din fiecare nod pleaca exact K arce de costuri 1,2...K (Cate un arc de fiecare cost). Pot exista arce multiple intre 2 noduri, si arce de la un nod la acelasi nod. Un drum este o succestiune de arce...care poate trece prin acelasi nod si prin aceeasi muchie de mai multe ori. Costul unui drum de lungime L este calculat astfel: Costul primului arc inmultit cu (K+1)^0^, adunat cu costul celui de-al doilea arc inmultit cu (K+1)^1^,... adunat cu costul celui de-al L-lea arc inmultit cu (K+1)^L-1^.

!home?graph.png!

!?graph.png!

Spre exemplu, pentru drumul de la 1 la 4 din graful din figura, costul acestui drum
pentru K = 3 este :
3*4 0 + 1*4 1 + 2*4 2 = 39