Dijkstra: بازیابی مسیر
Problem
یک نمودار وزنی جهت دار به شما داده می شود. کوتاه ترین مسیر را از یک راس داده شده به راس دیگر پیدا کنید.
ورودی
خط اول شامل سه عدد است: N، S و F (1≤N≤100، 1≤S، F≤N)، که در آن N – تعداد رئوس نمودار، S – راس اولیه، و F – نهایی در N سطر بعدی، هر کدام N عدد را وارد کنید که از 100 تجاوز نکند، – ماتریس مجاورت گراف، که در آن -1 به معنای عدم وجود لبه بین رئوس و هر عدد غیر منفی است – وجود لبه با وزن معین صفرها روی قطر اصلی ماتریس نوشته می شوند.
خروجی
لازم است تمام رئوس یک (هر) از کوتاهترین مسیرها به صورت متوالی نمایش داده شوند یا اگر مسیری بین رئوس مشخص شده وجود نداشته باشد یک عدد -1.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
3 2 1
0 1 1
4 0 1
2 1 0
|
2 3 1 |