بلمن
Problem
یک نمودار وزنی جهت دار با یال های منفی (بدون چرخه منفی) در نظر گرفته شده است.
با توجه به راس شروع و پایان، حداقل فاصله بین آنها را تعیین کنید.
ورودی:
با توجه به 4 عدد n، m، s، f - تعداد رئوس، تعداد یال ها، راس شروع و پایان (شروع از 1)، به ترتیب.
خطوط m بعدی هر کدام شامل 3 عدد هستند - راس 1، راس 2 و قیمت انتقال بین رئوس.
خروجی:
نمایش یک عدد - پاسخ به کار الزامی است. اگر پاسخی وجود ندارد، Inf را خروجی کنید.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
4 2 1 4
1 2 100500
2 3 100500
|
Inf |