Camí de cost mínim P64800


Statement
 

pdf   zip

thehtml

Escriviu un programa que, donat un graf dirigit amb costs positius als arcs, i dos vèrtexs x i ‍y, calculi un camí de cost mínim per anar des d’x fins a y. Si n’hi ha més d’un, cal triar el més petit en ordre lexicogràfic.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de vèrtexs n i el nombre d’arcs m. Segueixen m triplets u v c que indiquen que hi ha un arc uv de cost c, amb uv i 1 ≤ c ≤ 1000. Finalment, tenim x i y. Assumiu 1 ≤ n ≤ 104, 0 ≤ m ≤ 5n, i que per a tot parell de vèrtexs u i v hi ha com a molt un arc uv. Tots els nombres són enters. Els vèrtexs es numeren entre 0 i n−1.

Sortida

Per a cada cas, escriviu el cost del camí més barat per anar des d’x fins a y, seguit d’aquest camí. Si n’hi ha més d’un, escolliu el lexicogràficament més petit. Si no hi ha cap camí des d’x fins a y, indiqueu-ho.

Pista

Comenceu en y.

Public test cases
  • Input

    6 10
    1 0 6  1 5 15  3 4 3  3 1 8  4 0 20
    0 5 5  0 2 1  5 1 10  4 1 2  2 3 4
    3 5
    
    2 1
    0 1 1000
    1 0
    
    6 8
    4 0 7  0 2 3  4 3 5  3 2 4
    4 2 9  4 1 3  1 5 3  5 2 3
    4 2
    
    2 0
    1 1
    

    Output

    cost 16: 3 4 1 0 5
    no
    cost 9: 4 1 5 2
    cost 0: 1
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++