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


Problem

9 /10


فلوید - وجود

Theory Click to read/hide

مسیر عبور از چرخه وزن منفی غیرممکن می شود.

Problem

یک نمودار وزنی جهت دار به شما داده می شود. با استفاده از ماتریس مجاورت آن، باید برای هر جفت رئوس مشخص کنید که کوتاه ترین مسیر بین آنها وجود دارد یا خیر.
 
نظر: کوتاه ترین مسیر ممکن است به دو دلیل وجود نداشته باشد:
  • هیچ مسیری وجود ندارد
  • مسیرهایی با وزن کم دلخواه وجود دارد
     
ورودی
خط اول فایل ورودی حاوی یک عدد واحد است: N (1 <=N <=100) — تعداد رئوس نمودار N خط بعدی شامل N عدد هر کدام — ماتریس مجاورت گراف (عدد j در خط i با وزن یال از راس i تا راس j مطابقت دارد): عدد 0 به معنای بدون لبه است و هر عدد دیگری — وجود لبه وزن مربوطه. همه اعداد مدول از 100 تجاوز نمی کنند.
 
خروجی
N خط N عدد را چاپ کنید. عدد j در خط i باید با کوتاه ترین مسیر از راس i تا راس j مطابقت داشته باشد. اگر مسیری وجود ندارد، عدد باید 0، اگر کوتاه ترین مسیر وجود دارد، 1، و اگر مسیرهایی وجود دارد اما مسیرهایی با وزن کم دلخواه وجود دارد، باید 2 باشد.

نمونه‌ها <سر> <بدن>
# ورودی خروجی
1
5
0 1 2 0 0
1 0 3 0 0
2 3 0 0 0 0
0 0 0 0 -1
0 0 0 -1 0 
1 1 1 0 0 
1 1 1 0 0 
1 1 1 0 0 
0 0 0 2 2 
0 0 0 2 2 

time 1000 ms
memory 256 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!