Module: الگوریتم فلوید


Problem

2 /10


پرس و جوهای فلوید

Theory Click to read/hide

Problem

با توجه به یک نمودار وزنی بدون جهت با وزن های منفی، لازم است اطلاعاتی در مورد کوتاه ترین مسیر بین 2 راس خروجی داده شود.

ورودی
خط اول حاوی یک عدد صحیح n است - تعداد رئوس در نمودار. بعد، ورودی یک ماتریس مجاورت است که در آن -1 به معنای عدم وجود لبه بین رئوس. بعد از ماتریس یک عدد k وجود دارد - تعداد درخواست‌ها، خطوط بعدی k هر کدام شامل 2 عدد، a و b - رئوس در درخواست.

حصر
رشته باید حاوی اعداد k باشد - فاصله بین یک جفت اعداد از پرس و جو به ترتیبی که وارد می شوند، در صورتی که رسیدن از a بالای صفحه غیرممکن باشد. b بالا، سپس Imp را خروجی می‌کنید.
 
نمونه‌ها
<سر> <بدن>
# ورودی خروجی
1
3
0 3 -1
3 0 4
-1 4 0
3
1 3
3 2
1 2
 7
4
3

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!