Problem
Kebawah Duli Yang Maha Mulia Raja Bubei II ingin mengelilingi wilayahnya. Pada masa yang sama, laluan mempunyai kehendak berikut:
1) laluan harus mengambil masa yang paling sedikit (masa diraja – adalah perkara yang sangat berharga dan harus dilindungi);
2) laluan mesti termasuk semua penempatan tepat sekali (jika raja terlepas penempatan, maka penduduknya akan marah dengan ketidakpedulian diraja dan berhenti membayar cukai; jika raja melawat penempatan lebih daripada sekali, maka penduduk yang tinggal item penempatan juga akan marah)
3) laluan mesti bermula dan berakhir di ibu negara (setelah mengelilingi harta bendanya, raja mesti segera turun ke perniagaan). Ibu kota dimasukkan dalam laluan tepat 2 kali: sebagai titik berlepas dan sebagai destinasi, ia tidak boleh menjadi penyelesaian perantaraan laluan.
Tulis program yang menggunakan peta jalan kerajaan untuk mencari laluan sedemikian atau menentukan bahawa adalah mustahil untuk memenuhi semua keperluan.
Input
mula-mula masukkan nombor N (semula jadi, tidak melebihi 10) – bilangan petempatan dalam kerajaan. Kemudian mengikuti N baris N nombor dalam setiap – masa perjalanan antara penempatan (masa – ialah integer bukan negatif, tidak melebihi 500; jika masa = 0, maka ini bermakna tiada jalan antara beberapa penempatan). Petempatan No. 1 ialah ibu negeri.
Cetakan
cetak jumlah masa paling sedikit yang Baginda akan luangkan untuk melencong di sekitar domainnya, atau nombor -1 jika mustahil untuk membina laluan dengan hartanah yang diberikan.
Contoh
| # |
Input |
Output |
| 1 |
1
0 |
0 |
| 2 |
2
0 1
10 |
2 |
| 3 |
2
0 85
85 0 |
170 |