Գեղեցիկ

Կա $n$ քաղաքների մի շարք, որոնք միացված են երկկողմանի ճանապարհներով։ Ճանապարհները կարող են ունենալ տարբեր երկարություններ։ Ձեր խնդիրն է գտնել ամենակարճ ճանապարհը, որը անցնում է բոլոր քաղաքներով և վերադառնում մեկնարկային քաղաք։

Ձեզ տրված է n \times n մատրիցա $d$, որտեղ $d[i][j]$ արժեքը ցույց է տալիս $i$-րդ և $j$-րդ քաղաքների միջև ճանապարհի երկարությունը։ Ձեր խնդիրն է գտնել այնպիսի շրջանցում, որը սկսվում է որոշակի քաղաքից, անցնում է բոլոր քաղաքներով մեկ անգամ և վերադառնում է մեկնարկային քաղաք, այնպես որ ճանապարհի ընդհանուր երկարությունը լինի հնարավորինս փոքր։

Մուտք:

• Առաջին տողը պարունակում է մեկ ամբողջ թիվ $n$ (2 \leq n \leq 20)՝ քաղաքների քանակը։

• Հաջորդ $n$ տողերից յուրաքանչյուրը պարունակում է $n$ ամբողջ թվեր, որտեղ $j$-րդ թիվը $i$-րդ տողում ցույց է տալիս $d[i][j]$ արժեքը (1 \leq d[i][j] \leq 1000)։

Ելք:

• Տպեք մեկ ամբողջ թիվ՝ ամենակարճ շրջանցման ընդհանուր երկարությունը։