Module: Floyd's algorithm


Problem

2 /10


Floyd inquiries

Theory Click to read/hide

Problem

Given an undirected weighted graph with negative weights, it is necessary to output information about the shortest path between 2 vertices.

Input
The first line contains an integer n - the number of vertices in the graph. Next, the input is an adjacency matrix, in which -1 means the absence of an edge between the vertices. After the matrix there is a number k - the number of requests, the next k lines contain 2 numbers each, a and b - vertices in request.

Imprint
The string must contain k numbers - the distance between a pair of numbers from the query in the order they are entered, if it is impossible to get from the top a to the top b, then output Imp.
 
Examples
# Input Output
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!