Module: algoritmo de floyd


Problem

2 /10


consultas de floyd

Theory Click to read/hide

Problem

Dado un gráfico ponderado no dirigido con pesos negativos, es necesario generar información sobre el camino más corto entre 2 vértices.

Entrada
La primera línea contiene un número entero n: el número de vértices en el gráfico. A continuación, la entrada es una matriz de adyacencia, en la que -1 significa la ausencia de un borde entre los vértices. Después de la matriz hay un número k - el número de solicitudes, las siguientes líneas k contienen 2 números cada una, a y b - vértices en la solicitud.

Impresión
La cadena debe contener números k: la distancia entre un par de números de la consulta en el orden en que se ingresan, si es imposible llegar desde la parte superior a a la arriba b, luego salida Imp.
 
Ejemplos

time 1000 ms
memory 32 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
0 3 -1
3 0 4
-1 4 0
3
1 3
3 2
1 2
 7
4
3