الگوریتم دایکسترا در O(M logN)
Problem
برنامه ای بنویسید که فواصل را در یک گراف وزن دار بدون جهت با طول لبه های غیر منفی، از یک راس داده شده به هر راس دیگر، پیدا کند. این برنامه باید برای نمودارهای پراکنده بزرگ سریع باشد.
ورودی
خط اول ورودی حاوی عدد NUM — تعداد اجراهای مختلف الگوریتم دایکسترا (روی نمودارهای مختلف). به دنبال آن NUM بلوک وجود دارد که هر کدام ساختار زیر را دارند.
خط اول بلوک شامل دو عدد N و M است که با یک فاصله — تعداد رئوس و تعداد یال های نمودار. به دنبال آن خطوط M که هر کدام شامل سه عدد صحیح است که با فاصله از هم جدا شده اند، می آید. دو مورد اول از 0 تا N–1 هر کدام، نشان دهنده انتهای لبه مربوطه هستند، سومی — از 0 تا 20000 متغیر است و طول این لبه را نشان می دهد. علاوه بر این، در آخرین خط بلوک، یک عدد واحد از 0 تا N–1 — اوج، فاصله ای که باید از آن جستجو کنید.
تعداد نمودارهای مختلف در یک آزمون NUM از 5 تجاوز نمی کند. تعداد راس ها از 60000 تجاوز نمی کند، یال ها — 200000.
حصر
چاپ در خروجی استاندارد (صفحه نمایش) NUM خط، که هر کدام حاوی Ni اعداد جدا شده با فاصله — فاصله از راس شروع مشخص شده گراف بدون جهت وزنی تا 0، 1، 2 و غیره آن. رئوس (یک فاصله اضافی بعد از آخرین عدد مجاز است). اگر مقداری از راس از نقطه اولیه مشخص شده قابل دسترسی نیست، به جای فاصله، عدد 2009000999 را چاپ کنید (تضمین می شود که همه فواصل واقعی کمتر هستند).
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
1
5 7
1 2 5
1 3 2
2 3 4
2 4 3
3 4 6
0 3 20
0 4 10
1 |
18 0 5 2 8 |