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. En cada ciudad, un tanque de gasolina tiene un costo diferente. Necesitas ir de la primera ciudad a la N-ésima, gastando la menor cantidad de dinero posible. No puede comprar gasolina para uso futuro.
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 especifica el costo de la gasolina en la i-ésima ciudad (estos son números enteros 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 |
5
3 6 1 7 6
8
1 2
5 4
5 1
3 4
5 2
2 4
2 3
3 1
|
3 |