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

المپدیا

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

ابزار کاربر

ابزار سایت


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

Triangular Graph

مثلث خیام-پاسکال را در نظر بگیرید. فرض کنید هر کدام از اعداد این مثلث یک راس از یک گراف هستند. و هر راس (به جز رئوس سطر آخر) به رئوس سطر پایین خود که در سمت راست و چپ آن قرار دارند٬ یال جهت‌دار وزن‌دار دارند. یعنی هر راس دو یال دارد (به جز رئوس سطر آخر).

برنامه‌ای بنویسید که یک گراف با شرایط بالا را از ورودی بگیرد و طول کوتاه‌ترین مسیر از سطر اول به سطر آخر را بیابد.

ورودی

  • در نخستین سطر ورودی عدد n آمده است. که برابر تعداد سطرهای مثلث است.
  • سپس در n1 سطر وزن یال‌ها به این صورت آمده است که در سطر iام٬ i تا دوتایی به‌صورت (x,y) آمده است که دوتایی j ام در این سطر٬ به ترتیب وزن یال‌های سمت چپ و راست راس j ام در سطر i ام هستند. این دوتایی‌ها با یک فاصله از هم جدا شده اند.
  • 1n1000
  • وزن یال‌ها بین 1000 تا 1000 هستند.

خروجی

در تنها سطر خروجی طول کوتاه‌ترین مسیر از سطر اول به سطر آخر را چاپ کنید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
3
(0,-1)
(4,-1) (1,-1)
-2

پاسخ

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


ابزار صفحه