====== TSP ======

برنامه‌ای بنویسید که در یک گراف کامل بی‌جهت وزن‌دار $n$ راسی مسئله TSP (فروشنده‌ی دوره‌گرد) را حل کند. به عبارت دیگر دور همیلتونی با طول مینیمم را پیدا کند. 

برای این سوال باید یک الگوریتم backtrack با boundها و branch های مناسب بزنید تا time-limit نشوید.
===== ورودی ===== 
  * در سطر اول ورودی $n$ تعداد رئوس گراف نوشته شده است.
  * در هر یک از $n$ سطر بعد $n$ عدد آمده‌است. عدد $j$ام سطر $i$ام برابر $w_{ij}$ نشان‌دهنده‌ی وزن یال از راس $i$ام به راس $j$ام است. 
  * $1 \leq n \leq 30$
  * $1 \leq w_{ij} \leq 10^6$
  * $w_{ij} = w_{ji}$
===== خروجی ===== 
  * در سطر اول خروجی طول کوتاه‌ترین دور همیلتونی را بنویسید. 
  * در سطر دوم رئوس کوتاه‌ترین دور را به ترتیب بنویسید.
  * اولین راس مسیری که در خروجی می‌نویسید حتما باید راس شماره ۱ باشد.
===== محدودیت‌ها =====

  * محدودیت زمان: ۱ ثانیه
  * محدودیت حافظه: ۲۵۶ مگابایت

===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|3 \\ 0 2 1 \\ 2 0 2 \\ 1 2 0| 5 \\ 1 2 3 |
</WRAP>


<پاسخ>
منتظر پر کردن این قسمت توسط علاقمندان هستیم.
</پاسخ>

  * [[سوال ۵۱|سوال بعد]]
  * [[سوال ۴۹|سوال قبل]]