المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۹:سوال ۱۱

سوال ۱۱

شکل مقابل نقشه‌ی شهرهای یک کشور با جاده‌های بین آن‌ها را نشان می‌دهد. در این نقشه٬ نقاط توپر نشان‌دهنده‌ی شهرها و پاره‌خط‌های بین آن‌ها نشان‌دهنده‌ی جاده‌ها هستند. عددهای روی جاده‌ها٬ طول جاده‌ها برحسب کیلومتر را نشان می‌دهند. جهان‌گردی می‌خواهد از یکی از شهرها شروع کند و از همه‌ی شهرها بازدید کند.

او حداقل چند کیلومتر مسافت را باید طی کند؟

  1. ۴۵
  2. ۴۶
  3. ۴۷
  4. ۴۸
  5. ۵۰

پاسخ

گزینه (۳) درست است.

مسیری که طول آن ماکزیمم باشد مسیر اصلی در نظر می‌گیریم که با توجه به اعداد داده شده مسیر $fedhj$ مسیر اصلی می‌باشد. با محاسبه معلوم می‌شود که در این حالت مجموع مسافات پیموده شده برابر ۴۷ کیلومتر می‌شود.


ابزار صفحه