Module: L'algoritmo di Floyd


Problem

2 /10


Richieste Floyd

Theory Click to read/hide

Problem

Dato un grafico ponderato non orientato con pesi negativi, è necessario fornire informazioni sul percorso più breve tra 2 vertici.

Inserimento
La prima riga contiene un numero intero n - il numero di vertici nel grafico. Successivamente, l'input è una matrice di adiacenza, in cui -1 indica l'assenza di un bordo tra i vertici. Dopo la matrice c'è un numero k - il numero di richieste, le successive k righe contengono 2 numeri ciascuna, a e b - vertici in request.

Impressum
La stringa deve contenere k numeri - la distanza tra una coppia di numeri dalla query nell'ordine in cui sono stati inseriti, se è impossibile andare dall'alto a al top b, quindi output Imp.
 
Esempi
# Input Uscita
1
3
0 3 -1
3 0 4
-1 4 0
3
1 3
3 2
1 2
 7
4
3

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!