Masala E
Sayyoh Savdogar
Sizga N ta shahar va ularning orasidagi masofalar jadvali berilgan. Savdogar eng qisqa yo‘lni tanlab, barcha shaharlarni bir martadan bosib o‘tib, yana boshlang‘ich shaharga qaytishi kerak. Siz eng qisqa yo‘l uzunligini topishingiz kerak.
Kiruvchi ma'lumotlar:
Dastlab, bitta butun son N (2 ≤ N ≤ 10) – shaharlar soni beriladi.
Keyingi N qatorda N ta butun son bo‘lib, d[i][j] – i-shahardan j-shaharga bo‘lgan masofani bildiradi (0 ≤ d[i][j] ≤ 1000).
Shartlar:
- d[i][i] = 0 (o‘zidan o‘ziga borish mumkin emas).
- d[i][j] = d[j][i] (masofalar simmetrik).
Chiquvchi ma'lumotlar:
Eng qisqa sayohat uzunligi (barcha shaharlarni bir martadan bosib o‘tib, boshlang‘ich shaharga qaytish).
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
4 0 10 15 20 10 0 35 25 15 35 0 30 20 25 30 0 |
80 |
| 2 |
3 0 20 30 20 0 10 30 10 0 |
60 |
Telegram kanalimizga obuna bo'ling