Module: algoritmo de Floyd


Problem

2 /10


inquéritos Floyd

Theory Click to read/hide

Problem

Dado um grafo ponderado não direcionado com pesos negativos, é necessário fornecer informações sobre o caminho mais curto entre 2 vértices.

Entrada
A primeira linha contém um inteiro n - o número de vértices no grafo. Em seguida, a entrada é uma matriz de adjacência, na qual -1 significa a ausência de um borda entre os vértices. Após a matriz há um número k - o número de solicitações, as próximas k linhas contêm 2 números cada, a e b - vértices na requisição.

Impressão
A string deve conter números k - a distância entre um par de números da consulta na ordem em que são inseridos, se for impossível obter do a de cima para o top b, em seguida, imprima Imp.
 
Exemplos
# Entrada Saída
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!