Auftankungen
Problem
Es gibt N Städte im Land, von denen einige durch Straßen miteinander verbunden sind. Um die gleiche Straße zu befahren, ist ein Tank mit Benzin erforderlich. In jeder Stadt hat ein Benzintank unterschiedliche Kosten. Sie müssen von der ersten Stadt zur N-Ten gelangen und so wenig Geld wie möglich ausgeben. Sie können kein Benzin für die Zukunft kaufen.
Eingabe
In der ersten Zeile wird die Zahl N eingegeben (1≤N≤100), in der nächsten Zeile gibt es N Zahlen, von denen die i-ten den Benzinpreis in der i-ten Stadt angeben (dies sind ganze Zahlen zwischen 0 und 100). Dann kommt die Anzahl der M – die Anzahl der Straßen im Land, gefolgt von der Beschreibung der Straßen selbst. Jede Straße wird durch zwei Zahlen angegeben; die Städte, die sie verbindet. Alle Straßen sind beidseitig (das heißt, Sie können sowohl in eine als auch in die andere Richtung fahren), es gibt immer nicht mehr als eine Straße zwischen den beiden Städten, es gibt keine Straßen, die von der Stadt zu sich selbst führen.
Ausgabe
Sie müssen eine Zahl ausgeben, die Gesamtkosten der Route oder -1, wenn Sie nicht erreicht werden können.
Beispiele
| № |
Eingabe |
Ausgabe |
| 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 |