Planeación de Vacaciones (II)
Air Bovinia opera vuelos conectando las granjas en las que viven las vacas
. Como con cualquier aerolínea,
de esas granjas han sido designadas como centros
.
Actualmente, Air Bovinia ofrece vuelos de un sentido
, donde el vuelo
va de la granja
a la granja
a un costo de
dólares. Como en cualquier otra aerolínea sensible, para cada uno de estos viajes uno de
y
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 viajes de un sentido para las vacaciones de las vacas.
, donde el \(i-ésimo\) requerimiento es de la granja
a la granja
.
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 y
.
• Líneas 2…M+1: La línea contiene
,
y
. \((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 ).
• 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
\((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 1Salida
• 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
20Detalles de la Salida
Para el primer pasaje, la única ruta posible es ->
->
, costando
.
No hay vuelos saliendo de la granja , entonces las pobres vacas se quedan ahí atrapadas.
Comments
Marco_Escardon has este problema
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.
tengo dudas sobre que es MLE. Alguien me podria decir que es.
MLE = Memory Limit Exceeded