==Include(page="template/taskheader" task_id="dmin")==
 
==Include(page="template/raw")==
 
Link: [1]File-List
 
Drumuri minime
 
 
 
In anul 3000 oamenii locuiesc pe N planete. Pentru a putea calatori mai usor, oamenii au construit legaturi galactice bidirectionale intre anumite perechi de planete. Aceste legaturi sunt alimentate de un generator spatial, si se stie cate unitati energetice consuma transportul prin fiecare legatura. Se poate calatori intre oricare doua planete fie prin legaturi directe, fie trecand prin planete intermediare. Totusi, din motive inca necunoscute, se intampla ca atunci cand se circula consecutiv prin mai multe legaturi se consuma o cantitate de energie egala cu produsul costului energetic al fiecarei legaturi in parte. Pentru a face o statistica, conducatorul fortelor armate doreste sa stie cate drumuri distincte cu consum minim de energie exista intre planeta 1 si celelalte planete. Doua drumuri sunt distincte daca difera prin cel putin o legatura.
 
h2. Cerinta
 
Cunoscand numarul de planete, precum si legaturile dintre acestea impreuna cu costurile lor energetice, se cere sa afisati numarul de drumuri minime intre planeta 1 si celelalte planete. Fiecare numar va fi afisat modulo 104659.
 
h2. Date de Intrare
 
Pe prima linie a fisierului dmin.in se afla numerele N si M reprezentand numarul de planete, respectiv numarul de legaturi. Urmeaza M linii ce descriu legaturile dintre planete. Pe fiecare linie i sunt afisate cate trei numere x[i], y[i], c[i] cu semnificatia "exista o legatura intre planetele x[i] si y[i] ce are costul energetic c[i]".
 
h2. Date de Iesire
 
Pe prima linie a fisierului dmin.out sunt afisate N - 1 numere ce reprezinta numarul de drumuri minime intre planeta 1 si celelalte planete, numarul i reprezentand restul impartirii numarului de drumuri minime dintre planeta 1 si planeta i + 1 la 104659.
 
h2. Restrictii si precizari
 
&#159; 1 <= N <= 1500
 
&#159; 1 <= M <= 2500
 
&#159; costul energetic al unei legaturi este un numar intreg din intervalul [2, 10^9]
 
&#159; intre oricare doua planete poate exista cel mult o legatura
 
h2. Exemplu
 
dmin.in dmin.out Explicatie
8 9 1 1 2 2 2 2 4 Intre planetele 1 si 2 exista un singur drum minim de cost 2. Intre planetele 1 si 3 exista un singur drum minim de cost 3. Intre planetele 1 si 4 exista 2 drumuri minime de cost 6. Intre planetele 1 si 5 exista 2 drumuri minime de cost 24. Intre planetele 1 si 6 exista 2 drumuri minime de cost 48. Intre planetele 1 si 7 exista 2 drumuri minime de cost 72. Intre planetele 1 si 8 exista 4 drumuri minme de cost 144.
 
1 2 2
 
1 3 3
 
2 4 3
 
3 4 2
 
4 5 4
 
5 6 2
 
5 7 3
 
6 8 3
 
7 8 2
 
 
 
[
 
References
 
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/dmin/enunt_files/filelist.xml

==Include(page="template/taskheader" task_id="dmin")==
 
==Include(page="template/raw")==
 
In anul 3000 oamenii locuiesc pe $N$ planete. Pentru a putea calatori mai usor, oamenii au construit legaturi galactice bidirectionale intre anumite perechi de planete. Aceste legaturi sunt alimentate de un generator spatial, si se stie cate unitati energetice consuma transportul prin fiecare legatura. Se poate calatori intre oricare doua planete fie prin legaturi directe, fie trecand prin planete intermediare. Totusi, din motive inca necunoscute, se intampla ca atunci cand se circula consecutiv prin mai multe legaturi se consuma o cantitate de energie egala cu produsul costului energetic al fiecarei legaturi in parte. Pentru a face o statistica, conducatorul fortelor armate doreste sa stie cate drumuri distincte cu consum minim de energie exista intre planeta $1$ si celelalte planete. Doua drumuri sunt distincte daca difera prin cel putin o legatura.
 
h2. Cerinta
 
Cunoscand numarul de planete, precum si legaturile dintre acestea impreuna cu costurile lor energetice, se cere sa afisati numarul de drumuri minime intre planeta $1$ si celelalte planete. Fiecare numar va fi afisat modulo {$104659$}.
 
h2. Date de Intrare
 
Pe prima linie a fisierului dmin.in se afla numerele $N$ si $M$ reprezentand numarul de planete, respectiv numarul de legaturi. Urmeaza $M$ linii ce descriu legaturile dintre planete. Pe fiecare linie $i$ sunt afisate cate trei numere $x{~i~}, y{~i~}, c{~i~}$ cu semnificatia "exista o legatura intre planetele $x{~i~}$ si $y{~i~}$ ce are costul energetic {$c{~i~}$}".
 
h2. Date de Iesire
 
Pe prima linie a fisierului dmin.out sunt afisate $N-1$ numere ce reprezinta numarul de drumuri minime intre planeta $1$ si celelalte planete, numarul $i$ reprezentand restul impartirii numarului de drumuri minime dintre planeta $1$ si planeta $i+1$ la {$104659$}.
 
h2. Restrictii si precizari
 
* $1 ≤ N ≤ 1500$
* $1 ≤ M ≤ 2500$
* costul energetic al unei legaturi este un numar intreg din intervalul [{$2, 10^9^$}]
* intre oricare doua planete poate exista cel mult o legatura
 
h2. Exemplu
 
table(example). |_. dmin.in |_. dmin.out |
| 8 9
1 2 2
1 3 3
2 4 3
3 4 2
4 5 4
5 6 2
5 7 3
6 8 3
7 8 2
| 1 1 2 2 2 2 4 |
 
h3. Explicatie
 
* Intre planetele $1$ si $2$ exista un singur drum minim de cost {$2$}.
* Intre planetele $1$ si $3$ exista un singur drum minim de cost {$3$}.
* Intre planetele $1$ si $4$ exista $2$ drumuri minime de cost {$6$}.
* Intre planetele $1$ si $5$ exista $2$ drumuri minime de cost {$24$}.
* Intre planetele $1$ si $6$ exista $2$ drumuri minime de cost {$48$}.
* Intre planetele $1$ si $7$ exista $2$ drumuri minime de cost {$72$}.
* Intre planetele $1$ si $8$ exista $4$ drumuri minme de cost {$144$}.
 
 

==Include(page="template/taskfooter" task_id="dmin")==