Millor que Dijkstra P42012


Statement
 

pdf   zip

thehtml

Feu un programa que, donat un graf dirigit amb pesos que poden ser 1, 2 o 3, calculi el cost mínim d’anar del vèrtex 0 a la resta de vèrtexs.

Qui resolgui aquest problema amb l’algorisme de Dijkstra obtindrà com a molt un 7, perquè hi ha una manera asimptòticament millor.

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 indicant un arc uv de cost c, amb uv i 1 ≤ c ≤ 3. Assumiu 1 ≤ n ≤ 104, 0 ≤ m ≤ 5n, i que entre tot parell de vèrtexs u i v hi ha com a molt un arc uv. Els vèrtexs es numeren entre 0 i n−1.

Sortida

Per a cada cas, i per a cada vèrtex v, escriviu el cost mínim d’anar de 0 fins a v. Si és impossible, escriviu “no”. Escriviu una línia amb 10 guions al final de cada cas.

Public test cases
  • Input

    8 9
    0 6 1
    0 7 2
    0 4 3
    6 0 2
    6 1 1
    5 6 2
    1 2 1
    7 2 2
    4 2 3
    
    3 3
    0 2 1
    0 1 3
    2 1 1
    

    Output

    0 : 0
    1 : 2
    2 : 3
    3 : no
    4 : 3
    5 : no
    6 : 1
    7 : 2
    ----------
    0 : 0
    1 : 2
    2 : 1
    ----------
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++