Problem
Ülkede, bazıları karayoluyla birbirine bağlı N şehir vardır. Bir yolda sürmek için bir depo benzin gerekir. Her şehirde bir depo benzinin maliyeti farklıdır. Mümkün olduğunca az para harcayarak ilk şehirden N. şehire gitmeniz gerekiyor. İleride kullanmak üzere benzin satın alamazsınız.
Giriş
İlk satır N (1≤N≤100) sayısını içerir, sonraki satır i'incisi i'inci şehirdeki benzinin maliyetini belirten N sayıları içerir (bunlar 0'dan 100'e kadar olan tam sayılardır) ). Sonra M sayısı gelir – ülkedeki yolların sayısı, ardından yolların açıklamaları. Her yol iki sayı ile verilir – bağlandığı şehirlerin sayısı. Tüm yollar çift yönlüdür (yani hem bir yönde hem de diğer yönde sürülebilirler), iki şehir arasında her zaman birden fazla yol yoktur, şehirden kendisine giden yollar yoktur.
Çıktı
Tek bir sayı çıktısı almak için gereklidir – rotanın toplam maliyeti veya oraya ulaşmak imkansızsa -1.
Örnekler
| # |
Girdi |
Çıktı |
| 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 |