1-k BFS
Problem
یک نمودار وزنی جهت دار به شما داده می شود. باید با استفاده از الگوریتم 1 - k BFS، فاصله 1 بالا تا سایر موارد را پیدا کنید.
ورودی
اولین خط شامل 2 عدد صحیح n و m است که به ترتیب تعداد رئوس و یال‌های نمودار است. خطوط m بعدی شامل 3 عدد a و b هستند - رئوسی که لبه به هم متصل می‌کند و c - وزن این لبه (a, b, c >= 0).
خروجی
اگر مسیر ممکنی از 1 وجود نداشته باشد، باید عدد n-1 را با یک فاصله از هم جدا کنید - فواصل از بالای 1 تا سایر موارد به راس i، سپس باید Impossible را خروجی بگیرید.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
<پیش>
9 9
1 2 1
2 4 2
4 6 1
4 3 1
3 5 2
5 6 1
8 9 100
9 7 100
7 8 100
|
<پیش>
1 4 3 6 4 غیرممکن غیرممکن غیرممکن غیرممکن
|