Module: algoritmo de floyd


Problem

4 /10


el camino mas corto

Theory Click to read/hide

Si un gráfico tiene ciclos de peso negativo, formalmente el algoritmo de Floyd-Warshall no es aplicable a dicho gráfico.

De hecho, para aquellos pares de vértices i y j, entre los cuales es imposible entrar en un ciclo de peso negativo, el algoritmo funcionará correctamente.

Para los mismos pares de vértices para los que no hay respuesta (debido a la presencia de un ciclo negativo en el camino entre ellos), el algoritmo de Floyd encontrará algún número (posiblemente fuertemente negativo, pero no necesariamente) como respuesta. Sin embargo, el algoritmo de Floyd se puede mejorar para manejar dichos pares de vértices de forma ordenada y producir, por ejemplo,  \(- \infty\).

Para ello, por ejemplo, se puede realizar el siguiente criterio "inexistencia de la ruta". Entonces, deje que el algoritmo de Floyd habitual funcione en este gráfico. Entonces no hay camino más corto entre los vértices i y j si y solo si hay un vértice t accesible desde i y desde el cual se puede llegar a j, para el cual  \(d [t][t]<0\).

Además, al utilizar el algoritmo de Floyd para gráficas con ciclos negativos, se debe recordar que las distancias que surgen en el proceso de trabajo pueden ir negativamente, exponencialmente con cada fase. Por lo tanto, debe tener cuidado contra el desbordamiento de enteros limitando todas las distancias desde abajo a algún valor (por ejemplo,  \(- \infty\)).

Verbalmente, la solución se puede describir de la siguiente manera:
Después de que el algoritmo de Floyd-Warshall haya funcionado para el gráfico de entrada, iteremos sobre todos los pares de vértices \((i,j)\), y para cada uno de esos pares comprobamos, infinitamente el camino más corto de i a j es pequeño o no. Para hacer esto, iteremos sobre el tercer vértice t, y si resulta ser \(d[t][t] < 0\)  (es decir, se encuentra en el ciclo de peso negativo), y es accesible desde i y j — entonces la ruta \((i,j)\) puede tener una longitud infinitesimal.

Problem

Se le proporciona un gráfico completo dirigido con algunos pesos (longitudes) asignados a sus bordes. Los pesos pueden ser positivos, negativos o cero. Estamos interesados ​​en la longitud mínima de todos los caminos posibles entre todos los pares de vértices distintos en este gráfico. Habrá que averiguar si existe ese mínimo y, en caso afirmativo, calcularlo. (No hay un mínimo si es posible encontrar un camino de longitud negativa en el gráfico, arbitrariamente grande en valor absoluto, que tiende a infinito).
 
Entrada
La primera línea tiene N≤50 vértices. Luego viene la matriz de adyacencia del gráfico, es decir, N filas, cada una de las cuales contiene N números. El j-ésimo número en la i-ésima fila de la matriz de adyacencia especifica la longitud del borde que va desde el i-ésimo vértice hasta el j-ésimo. Las longitudes pueden tomar cualquier valor entre -1000000 y 1000000. Se garantiza que haya ceros en la diagonal principal de la matriz.
 
Salida
Imprimir un solo número – mínimo deseado. Si no existe, genera  -1.
Ejemplos
# Entrada Salida
1
3
0 42 18468
6335 0 26501
19170 15725 0
42
2
3
0 -7 3
-2 0 10
2 215 0
-1