Problem

6 /10


chu kỳ tiêu cực

Theory Click to read/hide

Do thuật toán Floyd giãn tuần tự khoảng cách giữa tất cả các cặp đỉnh (i, j), kể cả những cặp có i=j và khoảng cách ban đầu giữa một cặp đỉnh (i, i) bằng 0, nên chỉ có thể xảy ra giãn nếu đỉnh k sao cho d[i][k]+d[k][i]<0, tương đương với việc có một chu trình âm qua đỉnh i

Problem

Cho một đồ thị có hướng. Xác định xem nó có vòng lặp trọng lượng âm hay không.

Đầu vào
Dòng đầu tiên chứa số N (1 <= N <= 100) – số đỉnh của đồ thị. N dòng tiếp theo chứa N số, mỗi dòng – ma trận kề đồ thị. Trọng số của cạnh theo modulo nhỏ hơn 100000. Nếu không có cạnh nào, giá trị tương ứng là 100000.
 
Đầu ra
Trên dòng đầu tiên in "CÓ" nếu chu kỳ tồn tại hoặc "KHÔNG" nếu không. 

Ví dụ <đầu>

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!

# Đầu vào Đầu ra
1
3
100000 100000 -51
100  100000 100000
100000 -50  100000
 CÓ