Module: L'algoritmo di Floyd


Problem

7 /10


Ciclo negativo-2

Theory Click to read/hide

puoi leggere ulteriori informazioni su come trovare un ciclo negativo qui: http://e-maxx.ru/algo/export_ford_bellman

Problem

Dato un grafico orientato. Determina se ha un ciclo di peso negativo e, in tal caso, emettilo.
 
Input
La prima riga contiene il numero N (1 <= N <= 100) – il numero di vertici del grafo. Le successive N righe contengono N numeri ciascuna – matrice di adiacenza del grafo. Pesi degli spigoli modulo inferiori a 100000. Se non ci sono spigoli, il valore corrispondente è 100000.
 
Uscita
Sulla prima riga stampa "SI" se il ciclo esiste, altrimenti "NO". Se c'è un loop, nella seconda riga stampa il numero di vertici in esso (contando lo stesso – primo e ultimo), e nella terza riga – i vertici inclusi in questo ciclo sono in ordine di attraversamento. Se ci sono diversi cicli, allora  stampane uno qualsiasi.

Esempi
# Input Uscita
1
3
100000 100000 -51
100  100000 100000
100000 -50  100000
SÌ
4
3 2 1 3

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!