Millor que Dijkstra P42012

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 u → v de cost c, amb u ≠ v i 1 ≤ c ≤ 3. Assumiu 1 ≤ n ≤ 10⁴, 0 ≤ m ≤ 5n, i que entre tot parell de vèrtexs u i v hi ha com a molt un arc u → v. 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.