Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:سوال های تمرینی دوره ی تابستان:سوال ۵۰

TSP

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

برای این سوال باید یک الگوریتم backtrack با boundها و branch های مناسب بزنید تا time-limit نشوید.

ورودی

  • در سطر اول ورودی n تعداد رئوس گراف نوشته شده است.
  • در هر یک از n سطر بعد n عدد آمده‌است. عدد jام سطر iام برابر wij نشان‌دهنده‌ی وزن یال از راس iام به راس jام است.
  • 1n30
  • 1wij106
  • wij=wji

خروجی

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

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
3
0 2 1
2 0 2
1 2 0
5
1 2 3

پاسخ

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


ابزار صفحه