Nombre de camins mínims P77353


Statement
 

pdf   zip

thehtml

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.

Public test cases
  • 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
    
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++ Python