Module: Floyd's algorithm


Problem

6 /10


negative cycle

Theory Click to read/hide

Since Floyd's algorithm sequentially relaxes the distances between all pairs of vertices (i, j), including those with i=j, and the initial distance between a pair of vertices (i, i) is equal to zero, then relaxation can occur only if vertex k such that d[i][k]+d[k][i]<0, which is equivalent to having a negative cycle through vertex i

Problem

Given a directed graph. Determine if it has a negative weight cycle.

Input
The first line contains the number N (1 <= N <= 100) – the number of graph vertices. The next N lines contain N numbers each – graph adjacency matrix. Edge weights modulo less than 100000. If there is no edge, the corresponding value is 100000.
 
Output
On the first line print "YES" if the cycle exists, or "NO" otherwise. 

Examples
# Input Output
1
3
100000 100000 -51
100  100000 100000
100000 -50  100000
 YES

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!