Programozás‎ > ‎Feladatok‎ > ‎

Állatkert

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