Rutes Barates P40802


Statement
 

pdf   zip

html

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

P = [A, v1, …, vn, B]

és

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

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 ⟨Ai, Bi⟩, on Ai i Bi són vèrtexos del graf (0≤Ai,Bi<n).

Sortida Per a cada parell ⟨Ai, Bi⟩ de la seqüència d’entrada, el programa imprimeix el cost de la ruta més barata entre Ai i Bi. Si no hi ha cap ruta entre Ai i Bi el programa escriu c(Ai,Bi) = +oo. Per a cada cas s’escriu una línia acabada amb un salt de línia (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
    Catalan
    Translator
    Prof. EDA
    Original language
    English
    Other languages
    English Spanish
    Official solutions
    C++
    User solutions
    C++