Problem
Terdapat N bandar di negara ini, sebahagian daripadanya disambungkan melalui jalan raya. Ia memerlukan satu tangki petrol untuk memandu di satu jalan. Di setiap bandar, satu tangki petrol mempunyai kos yang berbeza. Anda perlu pergi dari bandar pertama ke bandar Nth, membelanjakan wang sesedikit mungkin. Anda tidak boleh membeli petrol untuk kegunaan masa hadapan.
Input
Baris pertama mengandungi nombor N (1≤N≤100), baris seterusnya mengandungi nombor N, ke-i yang menyatakan kos petrol di bandar ke-i (ini adalah integer dari 0 hingga 100 ). Kemudian datang nombor M – bilangan jalan di negara ini, diikuti dengan penerangan jalan itu sendiri. Setiap jalan diberi dua nombor – bilangan bandar yang disambungkannya. Semua jalan adalah dua hala (iaitu, ia boleh dipandu kedua-duanya dalam satu arah dan ke arah yang lain), sentiasa ada tidak lebih daripada satu jalan antara dua bandar, tidak ada jalan yang menghala dari bandar ke sendiri.
Output
Diperlukan untuk mengeluarkan satu nombor – jumlah kos laluan atau -1 jika mustahil untuk sampai ke sana.
Contoh
| # |
Input |
Output |
| 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 |