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}$

• در سطر اول خروجی طول کوتاه‌ترین دور همیلتونی را بنویسید.
• در سطر دوم رئوس کوتاه‌ترین دور را به ترتیب بنویسید.
• اولین راس مسیری که در خروجی می‌نویسید حتما باید راس شماره ۱ باشد.

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

• سوال بعد
• سوال قبل