Module: algoritmo de Floyd


Problem

7 /10


Ciclo Negativo-2

Theory Click to read/hide

você pode ler mais sobre como encontrar um ciclo negativo aqui: http://e-maxx.ru/algo/export_ford_bellman

Problem

Dado um grafo direcionado. Determine se ele tem um ciclo de peso negativo e, em caso afirmativo, imprima-o.
 
Entrada
A primeira linha contém o número N (1 <= N <= 100) – o número de vértices do gráfico. As próximas N linhas contêm N números cada – matriz de adjacência do grafo. Pesos da aresta módulo menor que 100.000. Se não houver aresta, o valor correspondente é 100.000.
 
Saída
Na primeira linha imprima "SIM" se o ciclo existir, ou "NÃO" caso contrário. Se houver um loop, na segunda linha imprima o número de vértices nele (contando o mesmo – primeiro e último), e na terceira linha – os vértices incluídos neste ciclo estão em ordem de travessia. Se houver vários ciclos, então  imprima qualquer um deles.

Exemplos
# Entrada Saída
1
3
100000 100000 -51
100  100000 100000
100000 -50  100000
SIM
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!