Module: Algoritma Floyd


Problem

7 /10


Kitaran Negatif-2

Theory Click to read/hide

anda boleh membaca lebih lanjut tentang mencari kitaran negatif di sini: http://e-maxx.ru/algo/export_ford_bellman

Problem

Diberi graf terarah. Tentukan sama ada ia mempunyai kitaran berat negatif, dan jika ya, keluarkannya.
 
Input
Baris pertama mengandungi nombor N (1 <= N <= 100) – bilangan bucu graf. N baris seterusnya mengandungi N nombor setiap satu – matriks bersebelahan graf. Modulo pemberat tepi kurang daripada 100000. Jika tiada tepi, nilai yang sepadan ialah 100000.
 
Output
Pada baris pertama cetak "YA" jika kitaran wujud, atau "TIDAK" sebaliknya. Jika terdapat gelung, dalam baris kedua cetak bilangan bucu di dalamnya (mengira yang sama – pertama dan terakhir), dan dalam baris ketiga – bucu yang termasuk dalam kitaran ini adalah dalam susunan traversal. Jika terdapat beberapa kitaran, maka  cetak mana-mana daripadanya.

Contoh

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!

# Input Output
1
3
100000 100000 -51
100  100000 100000
100000 -50  100000
YA
4
3 2 1 3