Nombre de camins mínims P77353
Donat un graf dirigit, calculeu per a cada vèrtex de quantes maneres s’hi pot arribar des del vèrtex 0 fent el mínim nombre de passos.
Entrada
L’entrada consisteix en diversos casos, cadascun amb el nombre de vèrtexos n (entre 1 i 104), el nombre d’arcs m (entre 0 i 10n), i m parells x y indicant que hi ha un arc de x a y. No hi ha arcs repetits, ni del tipus x x. Els vèrtexos es numeren de 0 a n − 1.
Sortida
Per a cada cas, i per a cada vèrtex x, escriviu el seu número, el mínim nombre de passos amb què es pot arribar a x sortint de 0, i de quantes maneres diferents es pot fer. Si un vèrtex és innaccessible des de 0, indiqueu-ho amb un -1. Escriviu una línia buida després de cada cas.
Input
4 3
0 1
1 2
2 3
2 0
8 15
0 1
0 2
1 3
1 4
2 3
2 4
3 5
3 6
4 5
4 6
5 7
5 1
6 7
6 2
1 0
Output
0: 0 1 1: 1 1 2: 2 1 3: 3 1 0: 0 1 1: -1 0: 0 1 1: 1 1 2: 1 1 3: 2 2 4: 2 2 5: 3 4 6: 3 4 7: 4 8
- Author
- Salvador Roura
- Language
- Catalan
- Other languages
- English
- Official solutions
- C++
- User solutions
- C++ Python