Rutas Baratas P40802


Statement
 

pdf   zip

html

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 positivos. Por lo tanto el coste de la ruta

P = [Av1, …, vnB]

es

  coste(P) = ω(A,v1) + ω(v1,v2) + … + ω(vn,B)  + ω′(v1)+…+ω′(vn).

Escribe un programa en C++ que, dados un garfo no dirigido con pesos positivos 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 positivos. La entrada comienza con dos enteros 2≤n≤10000 y m, 0≤m≤20n. A continuación, viene una secuencia de n enteros positivos ω′(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 positivos. Ningún peso, ni de aristas ni de vértices, es mayor que 100000. 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 ⟨Ai, Bi⟩, donde los Ai’s y los Bi’s denotan vértices del grafo (0≤Ai,Bi<n).

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

Public test cases
  • Input

    6 8
    3 6 10 15 5 2
    0 1 2  1 2 7  2 3 2 
    0 2 1  1 3 4  2 4 8
    3 4 2  3 0 5
    0 4
    1 4
    2 4
    3 1 
    4 1
    2 5
    2 2
    
    

    Output

    c(0,4) = 19
    c(1,4) = 21
    c(2,4) = 8
    c(3,1) = 4
    c(4,1) = 21
    c(2,5) = +oo
    c(2,2) = 0
    
  • Information
    Author
    Prof. EDA
    Language
    Spanish
    Translator
    Prof. EDA
    Original language
    English
    Other languages
    Catalan English
    Official solutions
    C++
    User solutions
    C++