Dijkstra, tal qual P30288


Statement
 

pdf   zip

thehtml

Feu un programa que calculi el cost mínim d’anar d’un vèrtex a tots els altres en un graf dirigit amb pesos positius als arcs.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de vèrtexs n i el nombre d’arcs m, seguits de m triplets x y c, que indiquen que hi ha un arc de x a y que té cost ‍c. Suposeu 2 ≤ n ≤ 104, 0 ≤ m ≤ 5n, que els vèrtexs es numeren entre 0 i n − 1, xy, que per a tot parell x y no hi ha més d’un arc d’anada i un de tornada, i que tots els costs c són naturals entre 1 i 104.

Sortida

Per a cada cas, escriviu el cost mínim d’anar de 0 a cadascun dels altres vèrtexs, en ordre de 1 a n − 1. Si no hi ha camí fins a algun vèrtex, indiqueu-ho escrivint “no”. Escriviu una línia amb 10 guions al final de cada cas.

Public test cases
  • Input

    4 3
    0 1 100
    0 3 200
    1 3 50
    
    2 1
    1 0 10000
    

    Output

    100
    no
    150
    ----------
    no
    ----------
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++