Module: algoritmo de floyd


Problem

7 /10


Ciclo negativo-2

Theory Click to read/hide

puede leer más sobre cómo encontrar un ciclo negativo aquí: http://e-maxx.ru/algo/export_ford_bellman

Problem

Dada una gráfica dirigida. Determine si tiene un ciclo de peso negativo y, de ser así, envíelo.
 
Entrada
La primera línea contiene el número N (1 <= N <= 100) – el número de vértices del gráfico. Las siguientes N líneas contienen N números cada una – matriz de adyacencia de grafos. Los pesos de borde tienen un módulo inferior a 100000. Si no hay borde, el valor correspondiente es 100000.
 
Salida
En la primera línea escriba "SÍ" si el ciclo existe, o "NO" en caso contrario. Si hay un bucle, en la segunda línea escribe el número de vértices que hay en él (contando lo mismo – primero y último), y en la tercera línea – los vértices incluidos en este ciclo están en orden transversal. Si hay varios ciclos, entonces  imprima cualquiera de ellos.

Ejemplos

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!

# Entrada Salida
1
3
100000 100000 -51
100  100000 100000
100000 -50  100000
SÍ
4
3 2 1 3