Problem

9 /10


فلويد - الوجود

Theory Click to read/hide

يصبح المسار عبر دورة الوزن السلبي مستحيلاً.

Problem

يتم إعطاؤك رسم بياني مرجح موجه. باستخدام مصفوفة تجاورها ، تحتاج إلى تحديد لكل زوج من الرؤوس ما إذا كان هناك أقصر مسار بينهما أم لا.
& nbsp؛
تعليق: قد لا يوجد أقصر طريق لسببين:
  • لا توجد مسارات
  • هناك مسارات ذات وزن صغير بشكل تعسفي
    نبسب ؛
إدخال
يحتوي السطر الأول من ملف الإدخال على رقم واحد: N (1 & lt؛ = N & lt؛ = 100) & mdash؛ عدد رؤوس الرسم البياني. تحتوي الأسطر N التالية على أرقام N لكل منها & [مدش]؛ مصفوفة تجاور الرسم البياني (الرقم j في السطر الأول يتوافق مع وزن الحافة من الرأس i إلى الرأس j): الرقم 0 يعني عدم وجود حافة وأي رقم آخر & mdash ؛ وجود حافة للوزن المقابل. جميع أرقام modulo لا تتجاوز 100.
& nbsp؛
الإخراج
طباعة N سطور من N أرقام. يجب أن يتوافق الرقم j في السطر الأول مع أقصر مسار من الرأس 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 -1
0 0 0-1 0 & nbsp؛
1 1 1 0 0 & nbsp؛
1 1 1 0 0 & nbsp؛
1 1 1 0 0 & nbsp؛
0 0 0 2 2 & nbsp؛
0 0 0 2 2 & nbsp؛

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!