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. Inoltre, hai una bombola di gas che contiene la stessa quantità di carburante di un serbatoio di benzina.
In ogni città, un pieno di benzina ha un costo diverso. Devi andare dalla prima città all'ennesima, spendendo il meno possibile.
In ogni città puoi riempire il serbatoio, riempire il serbatoio e la tanica o versare benzina dalla tanica nel serbatoio. Questo ti permette di risparmiare acquistando benzina in quelle città dove costa meno, ma la tanica è sufficiente solo per un pieno di carburante!
Input
La prima riga contiene il numero N (1<=N<=100), la riga successiva contiene N numeri, l'i-esimo dei quali imposta il costo della benzina nella i-esima città (tutti questi sono numeri interi da l'intervallo 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, oppure -1 se è impossibile arrivarci.
Esempi
| # |
Input |
Uscita |
| 1 |
4
1 10 2 15
4
1 2
1 3
4 2
4 3
|
2 |