Problem
Majesteleri Kral Bubei II, kendi bölgesini dolaşmak istedi. Aynı zamanda rotanın şu istekleri var:
1) rota mümkün olan en kısa sürede yapılmalıdır (kraliyet zamanı – çok değerli bir şeydir ve korunmalıdır);
2) rota, tüm yerleşim yerlerini tam olarak bir kez içermelidir (kral bir yerleşim yerini kaçırırsa, o zaman sakinleri kraliyet dikkatsizliğinden öfkelenecek ve vergi ödemeyi bırakacaktır; eğer kral bir yerleşim yerini birden fazla ziyaret ederse, o zaman kalan yerleşimin sakinleri yerleşim öğeleri de kızacak)
3) rota devletin başkentinde başlamalı ve bitmelidir (mallarının etrafında dolaştıktan sonra kral hemen işe başlamalıdır). Başkent rotaya tam olarak 2 kez dahil edilir: kalkış noktası ve varış noktası olarak rotanın ara yerleşim yeri olamaz.
Böyle bir rota bulmak için krallığın yol haritasını kullanan veya tüm gereksinimleri yerine getirmenin imkansız olduğunu belirleyen bir program yazın.
Girdi
önce N sayısını girin (doğal, 10'u geçmez) – ndash; krallıktaki yerleşim sayısı. Ardından, her bir – yerleşim yerleri arasındaki seyahat süresi (zaman - negatif olmayan bir tam sayıdır, 500'ü geçmez; eğer zaman = 0 ise bu, bazı yerleşim yerleri arasında yol olmadığı anlamına gelir). 1 Nolu Yerleşim Devletin başkentidir.
Künye
Majestelerinin kendi bölgeleri etrafında bir dolambaçlı yol için harcayacağı en az toplam süreyi veya verilen özelliklerle bir rota oluşturmak imkansızsa -1 sayısını yazdırın.
Örnekler
| # |
Girdi |
Çıktı |
| 1 |
1
0 |
0 |
| 2 |
2
0 1
10 |
2 |
| 3 |
2
0 85
85 0 |
170 |