Triangular Graph
مثلث خیام-پاسکال را در نظر بگیرید. فرض کنید هر کدام از اعداد این مثلث یک راس از یک گراف هستند. و هر راس (به جز رئوس سطر آخر) به رئوس سطر پایین خود که در سمت راست و چپ آن قرار دارند٬ یال جهتدار وزندار دارند. یعنی هر راس دو یال دارد (به جز رئوس
سطر آخر).
برنامهای بنویسید که یک گراف با شرایط بالا را از ورودی بگیرد و طول کوتاهترین مسیر از سطر اول به سطر آخر را بیابد.
ورودی
در نخستین سطر ورودی عدد n آمده است. که برابر تعداد سطرهای مثلث است.
سپس در n−1 سطر وزن یالها به این صورت آمده است که در سطر iام٬ i تا دوتایی بهصورت (x,y) آمده است که دوتایی j ام در این سطر٬ به ترتیب وزن یالهای سمت چپ و راست راس j ام در سطر i ام هستند. این دوتاییها با یک فاصله از هم جدا شده اند.
1≤n≤1000
وزن یالها بین −1000 تا 1000 هستند.
خروجی
در تنها سطر خروجی طول کوتاهترین مسیر از سطر اول به سطر آخر را چاپ کنید.
محدودیتها
ورودی و خروجی نمونه
ورودی نمونه | خروجی نمونه |
3
(0,-1)
(4,-1) (1,-1) | -2 |
پاسخ
منتظر پر کردن این قسمت توسط علاقمندان هستیم.