Problem
Ci sono N città nel paese, alcune delle quali sono collegate da strade. Ci vuole un pieno di benzina per guidare su una strada. In ogni città un pieno di benzina ha un costo diverso. Devi andare dalla prima città all'ennesima, spendendo il meno possibile. Non puoi acquistare benzina per un uso futuro.
Input
La prima riga contiene il numero N (1≤N≤100), la riga successiva contiene N numeri, l'i-esimo dei quali specifica il costo della benzina nella città i-esima (si tratta di numeri interi da 0 a 100 ). Poi arriva il numero M – il numero di strade del paese, seguito da una descrizione delle strade stesse. Ogni strada è data da due numeri – i numeri delle città che collega. Tutte le strade sono a doppio senso (cioè possono essere percorse sia in una direzione che nell'altra), non c'è sempre più di una strada tra due città, non ci sono strade che portano dalla città a se stessa.
Uscita
Obbligatorio per produrre un singolo numero – il costo totale del percorso o -1 se è impossibile arrivarci.
Esempi
| # |
Input |
Uscita |
| 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 |