Problem
Hay N ciudades en el país, algunas de las cuales están conectadas por carreteras. Se necesita un tanque de gasolina para conducir en una carretera. Además, tiene un bote de gasolina que contiene la misma cantidad de combustible que un tanque de gasolina.
En cada ciudad, un tanque de gasolina tiene un costo diferente. Tienes que ir de la primera ciudad a la enésima, gastando la menor cantidad de dinero posible.
En cada ciudad, puede llenar el tanque, llenar el tanque y el bote, o verter gasolina del bote al tanque. Esto le permite ahorrar dinero comprando gasolina en aquellas ciudades donde es más barata, ¡pero el bote solo es suficiente para llenar un tanque!
Entrada
La primera línea contiene el número N (1<=N<=100), la siguiente línea contiene N números, el i-ésimo de los cuales establece el costo de la gasolina en la i-ésima ciudad (todos estos son números enteros de el rango de 0 a 100). Luego viene el número M – el número de caminos en el país, seguido de una descripción de los caminos mismos. Cada camino está dado por dos números – los números de las ciudades que conecta. Todas las carreteras son de doble sentido (es decir, se pueden conducir tanto en un sentido como en el otro sentido), siempre no hay más de un camino entre dos ciudades, no hay caminos que lleven de la ciudad a sí misma.
Salida
Requerido para generar un solo número – el costo total de la ruta, o -1 si es imposible llegar.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
4
1 10 2 15
4
1 2
1 3
4 2
4 3
|
2 |