TSP-hard

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

برای این مسئله شما باید از روش Simulated Annealing استفاده کنید. دقت کنید با توجه به اینکه برای پاسخ گویی به هر تست شما ۳ ثانیه وقت دارید می‌توانید به مقدار مناسبی برنامه‌ی Simul خود را اجرا کنید.

• در سطر اول ورودی $n$ تعداد رئوس گراف نوشته شده است.
• در هر یک از $n$ سطر بعد $n$ عدد آمده‌است. عدد $j$ام سطر $i$ام برابر $w_{ij}$ نشان‌دهنده‌ی وزن یال از راس $i$ام به راس $j$ام است.
• $1 \leq n \leq 100$
• $1 \leq w_{ij} \leq 10^6$
• $w_{ij} = w_{ji}$

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

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

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