فورد بلمن
Problem
یک نمودار جهت دار داده می شود که می تواند چندین یال و حلقه داشته باشد. هر یال دارای وزنی است که به صورت یک عدد صحیح بیان می شود (احتمالاً منفی). تضمین شده است که هیچ چرخه وزن منفی وجود ندارد.
شما باید طول کوتاه ترین مسیرها را از راس شماره 1 تا همه رئوس دیگر محاسبه کنید.
ورودی
برنامه ابتدا عدد N (1 <= N <= 100) – تعداد رئوس نمودار و عدد M (0 <= M <= 10000) – تعداد دنده ها خطوط زیر حاوی M سه عدد از اعداد است که لبه ها را توصیف می کنند: ابتدای یال، انتهای لبه و وزن (وزن – یک عدد صحیح از 100- تا 100 است).
خروجی
برنامه باید N عدد – فاصله از راس شماره 1 تا تمام رئوس نمودار. اگر مسیری به راس مربوطه وجود ندارد، به جای طول مسیر، عدد 30000 را چاپ کنید.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
|
0 10 20 30000 30000 30000 |