Egy állatkertben ismerjük a bejárható útvonalakat. A bejárat a 0-s sorszámú pont. Az egyes állatokat az 1 és N közötti sorszámukkal azonosítjuk, az utakat pedig két olyan állat sorszámával, amelyek ketrece között vezetnek. A látogatók szeretnének bizonyos állatokhoz a lehető legrövidebb úton eljutni.
Feladat
Írjunk programot, ami az állatkerti utak ismeretében megadja, hogy a bejárattól melyik állathoz hányféleképpen lehet a lehető legrövidebb úton eljutni.
Bemenet
A bemenet első sorában az állatok N száma (1<= N <= 40) és az utak M száma (1 <= M <= 1000) van. A következő M sorban egy-egy út leírása található: azon két állat sorszáma, amelyek között az út vezet.
Kimenet
N sort kell kiírni. Az i-dik sorba a bejárattól az i sorszámú állathoz vezető legrövidebb utak száma kerüljön!
Példa
Bemenet |
Kimenet |
5 7 0 1 1 4 3 1 3 5 2 0 2 3 4 5 | 1 1 2 1 3
|
Tesztadatok
Címkék
A feladat forrása: NTOITV 9-10. évfolyam, 2012 3. forduló
Algoritmusok: gráfbejárás
megoldás |