Viaje por Europa
Dosberto después de revisar los recibos de su viaje en automóvil por Europa este verano, se dio cuenta de que los precios de la gasolina variaban entre las ciudades que visitaba. ¿Quizás podría haber ahorrado algo de dinero si fuera un poco más inteligente acerca de dónde llenó el combustible? Para ayudar a otros turistas (y ahorrar dinero la próxima vez), desea escribir un programa para encontrar la forma más barata de viajar entre ciudades, llenando su tanque en el camino. Suponemos que todos los automóviles usan una unidad de combustible por unidad de distancia y comienzan con un tanque de gasolina vacío.
Entrada
La primera línea de entrada contiene a y , el número de ciudades y carreteras. Luego sigue una línea con números enteros , donde es el precio de una unidad de combustible en la i-ésima ciudad. Luego siguen líneas con tres números enteros y , indicando que hay una carretera entre y con longitud . Luego viene una línea con el número , dando el número de consultas, y líneas con tres enteros , y , donde es la capacidad de combustible del vehículo, es la ciudad de partida , y es la ciudad a la que se quiere llegar.
Salida
Para cada consulta, genere el precio del viaje más barato de a usando un automóvil con la capacidad dada, o "impossible" si no hay forma de ir de a con el automóvil dado.
Ejemplo de Entrada
5 5
10 10 20 12 13
0 1 9
0 2 8
1 2 1
1 3 11
2 3 7
2
10 0 3
20 1 4
Ejemplo de Salida
170
impossible
Comments