Camí més curt P81453


Statement
 

pdf   zip

html

Feu un programa que, donat un graf dirigit amb n vèrtexs (numerats entre 0 i n−1) i m arcs, escrigui el camí més curt per anar de 0 a n−1.

Entrada

L’entrada consisteix en diversos casos. Cadascun comença amb n i m. Segueixen m parells x y indicant un arc de x a y. No hi ha arcs repetits ni del tipus x x. Sempre hi ha algun camí entre 0 i n−1. Podeu suposar 2 ≤ n ≤ 104 i 1 ≤ m ≤ 5n.

Sortida

Per a cada cas, escriviu els vèrtexs del camí més curt entre 0 i n−1 separats amb espais. Si hi ha més d’un camí mínim, escriviu el més petit en ordre lexicogràfic.

Public test cases

  • Input

    10 11
8 2  0 1  4 0  1 4  3 9  4 6
6 9  0 8  2 9  0 7  7 3

2 2
1 0  0 1

    Output

    0 7 3 9
0 1
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++