Problem

6 /10


دورة سلبية

Theory Click to read/hide

نظرًا لأن خوارزمية Floyd ترخي بالتتابع المسافات بين جميع أزواج القمم (i ، j) ، بما في ذلك تلك التي تحتوي على i = j ، والمسافة الأولية بين زوج من القمم (i ، i) تساوي صفرًا ، عندئذٍ يمكن أن يحدث الاسترخاء فقط إذا كان الرأس k مثل d [i] [k] + d [k] [i] & lt؛ 0 ، وهو ما يعادل وجود دورة سالبة من خلال الرأس i

Problem

إعطاء رسم بياني موجه. حدد ما إذا كانت حلقة الوزن السالبة.

إدخال
يحتوي السطر الأول على الرقم N (1 & lt؛ = N & lt؛ = 100) & ndash؛ عدد رؤوس الرسم البياني. الأسطر N التالية تحتوي على أرقام N لكل منها & ndash؛ مصفوفة تجاور الرسم البياني. مقاييس أوزان الحواف أقل من 100000. في حالة عدم وجود حافة ، تكون القيمة المقابلة 100000.
& nbsp؛
الإخراج
في السطر الأول ، اطبع "YES" إذا كانت الدورة موجودة ، أو "NO" بخلاف ذلك. & nbsp؛

أمثلة <الجسم>
# إدخال الإخراج
1
3
100000 100000-51
100 نبسب ؛ 100000 100000
100000-50 نبسب ؛ 100000
نعم

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!