Rutes Barates P40802

Hem recollit abundant informació sobre les carreteres locals i allotjaments d’una regió que ens proposem recórrer. El nostre objectiu és anar de la ciutat A a la ciutat B i ens agradaria fer el mínim de despeses. Per a cada carretera que connecta dues ciutats u i v sabem el cost ω(u,v)=ω(v,u) de viatjar per aquesta carretera (peatges, gasolina, àpats durant el camí, …). Cada cop que anem d’una ciutat u a una de les seves veïnes v haurem de fer nit; també sabem el cost ω′(v) d’aturar-se per fer nit a cada ciutat v (el cost afegit per A i B al cost de la nostra ruta és 0, doncs són els punts d’origen i de destí).

Tots els costos, tant del vèrtexos com de les arestes, són positius. Així doncs, el cost de la ruta

és

Escriu un programa en C++ que, donat un graf no dirigit amb pesos positius als vèrtexos i les arestes i dos vèrtexos A i B, calcula el cost de la ruta més barata per anar d’A a B, o bé ens indica que no existeix cap ruta.

Entrada Totes les dades d’entrada són enters positius. L’entrada comença amb dos enters 2≤n≤10000 i m, 0≤m≤20n. A continuació, vindrà una seqüència d’enters positius ω′(0), …, ω′(n−1) dels costos ω′(u) dels n vèrtexos del graf. Després l’entrada conté la seqüència d’arestes del graf en forma de tripletes ⟨u,v,ω(u,v)⟩. Els vèrtexos u i v són enters en el rang {0,…,n−1} i els costos ω(u,v) són enters positius. Cap pes, sigui d’arestes, sigui de vèrtexos, és més gran que 100000.

Pots assumir que no hi haurà arestes diferents connectant un mateix de vèrtexos ni cap aresta que connecta un vèrtex amb si mateix.

Finalment, l’entrada conté una seqüència de parells ⟨A_i, B_i⟩, on A_i i B_i són vèrtexos del graf (0≤A_i,B_i<n).

Sortida Per a cada parell ⟨A_i, B_i⟩ de la seqüència d’entrada, el programa imprimeix el cost de la ruta més barata entre A_i i B_i. Si no hi ha cap ruta entre A_i i B_i el programa escriu c(A_i,B_i) = +oo. Per a cada cas s’escriu una línia acabada amb un salt de línia (endl).