Planeación de Vacaciones (II)

Submit solution
Points: 100 (partial)
Time limit: 4.0s
Memory limit: 256M
Author:
antonio_bouza
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Swift, VB

Air Bovinia opera vuelos conectando las N granjas en las que viven las vacas (1 \leq N \leq 20 000). Como con cualquier aerolínea, K de esas granjas han sido designadas como centros (1 \leq K \leq 200, K \leq N).

Actualmente, Air Bovinia ofrece M vuelos de un sentido (1 \leq M \leq 20 000), donde el vuelo i va de la granja u_i a la granja v_i a un costo de d_i (1 \leq d_i \leq 10 000) dólares. Como en cualquier otra aerolínea sensible, para cada uno de estos viajes uno de u_i y v_i es un centro. Hay a lo más un vuelo directo entre dos granjas en cualquier dirección dada y ningún vuelo comienza y termina en la misma granja.

Bessie está a cargo de administrar los servicios de pasajes para Air bovinia. Desafortunadamente, mientras ella estaba rumiando heno delicioso por horas, llegaron requerimientos de Q viajes de un sentido para las vacaciones de las vacas. (1 \leq Q \leq 50 000), donde el \(i-ésimo\) requerimiento es de la granja a_i a la granja b_i.

Como Bessie está sobrecargada con la tarea de procesar esos pasajes, por favor ayúdela a calcular si cada requerimiento de pasaje puede ser satisfecho y su costo mínimo si puede ser hecho.

Para reducir el tamaño de la salida, usted debe dar como salida únicamente el número total de requerimientos de pasajes que son posibles y el costo mínimo total para ellos. Note que este número podría no entrar en un entero de 32 bits.

Entrada

• Línea 1: Los enteros N, M, K y Q.

• Líneas 2…M+1: La línea i+1 contiene u_i, v_i y d_i. \((1 \leq u_i, v_i \leq N, u_i ≠ v_i)\).

• Líneas M+2…M+K+1: Cada una de esas líneas contiene el identificador de un solo centro (en el rango 1...N).

• Líneas M+K+2...M+K+Q+1: Dos números por línea, indicando un requerimiento para un pasaje de la granja a_i a b_i \((1 \leq a_i, b_i \leq N, a_i ≠ b_i)\).

Ejemplo de Entrada

3 3 1 2
1 2 10
2 3 10
2 1 5
2
1 3
3 1

Salida

• Línea 1: El número de pasajes requeridos que pueden ser satisfechos.

• Línea 2: El mínimo costo total de cumplir los requerimientos posibles de pasajes.

Ejemplo de Salida

1
20

Detalles de la Salida

Para el primer pasaje, la única ruta posible es 1->2->3, costando 20.

No hay vuelos saliendo de la granja 3, entonces las pobres vacas se quedan ahí atrapadas.

Comments


  • 0
    Maite  commented on Jan. 29, 2023, 2:46 a.m.

    Marco_Escardon has este problema


  • 1
    Osnielfc_07  commented on Nov. 24, 2020, 6:11 p.m.

    Estoy preguntando esto porque este problema me da MLE y me imagino que es porque el resultado es demasiado grande. Si es por esto alguien me podria decir un modulo para ir moduleando la suma de las distancias o otra de forma de reducir el tamaño de esta suma.


  • 1
    Osnielfc_07  commented on Nov. 24, 2020, 6:07 p.m.

    tengo dudas sobre que es MLE. Alguien me podria decir que es.


    • 2
      josed  commented on Nov. 24, 2020, 7:38 p.m.

      MLE = Memory Limit Exceeded