Rutas Baratas X81287

Hemos recopilado abundante información sobre las carreteras locales y alojamientos de una cierta región que queremos visitar. Nuestro plan es ir de una ciudad A a otra ciudad B, gastando la menor cantidad de dinero posible. Para toda carretera que conecta dos ciudades u y v sabemos el coste ω(u,v)=ω(v,u) de viajar por dicha carretera (peajes, gasolina, comidas durante el viaje, …). Cada vez que viajamos de una ciudad u a una de sus vecinas v debemos parar en v y hacer noche; sabemos los costes ω′(v) de pernoctar para todas las ciudades v (el coste añadido por A y B a nuestra ruta es 0, ya que son los puntos de origen y de destino). Todos los costes, de vértices y de aristas, son no negativos. Por lo tanto el coste de la ruta

es

Escribe un programa en C++ que, dados un garfo no dirigido con pesos no negativos en vértices y en aristas, y dos vértices A y B, devuelve el coste de la ruta más barata para ir de A a B, o una indicación de que no existe tal ruta.

Entrada Todos los datos de entrada son enteros no negativos. La entrada comienza con dos enteros 2≤n≤10000 y m, 0≤m≤20n. A continuación, viene una secuencia de n enteros no negativos ω′(0), …, ω′(n−1), los pesos ω′(u) de los n vértices del grafo. Luego viene una secuencia con las m aristas del grafo en forma de tripletas ⟨u,v,ω(u,v)⟩. Los vértices u y v son enteros en el rango {0,…,n−1} y los pesos ω(u,v) son enteros no negativos. Puede asumirse que no hay aristas paralelas diferentes uniendo un mismo par de vértices y que no hay ninguna arista que une a un vértice consigo mismo. Finalmente, la entrada contiene una secuencia de pares ⟨A_i, B_i⟩, donde los A_i’s y los B_i’s denotan vértices del grafo (0≤A_i,B_i<n).

Salida Para cada par ⟨A_i, B_i⟩ de la entrada, el programa escribe el coste δ de la ruta más barata entre A_i y B_i con el formato c(A_i,B_i) = δ. Si no hay rutas entre A_i y B_i el programa escribe c(A_i,B_i) = +oo. Cada línea de la salida termina con un salto de línea (endl).