Problem

2 /10


Demandes Floyd

Theory Click to read/hide

Problem

Étant donné un graphe pondéré non orienté avec des poids négatifs, il est nécessaire de sortir des informations sur le chemin le plus court entre 2 sommets.

Entrée
La première ligne contient un entier n - le nombre de sommets dans le graphe. Ensuite, l'entrée est une matrice d'adjacence, dans laquelle -1 signifie l'absence d'un bord entre les sommets. Après la matrice, il y a un nombre k - le nombre de requêtes, les lignes k suivantes contiennent chacune 2 nombres, a et b - sommets dans la requête.

Mentions légales
La chaîne doit contenir des nombres k - la distance entre une paire de nombres de la requête dans l'ordre dans lequel ils sont entrés, s'il est impossible d'aller du haut a au top b, puis sortie Imp.
 
Exemples
3
0 3 -1
3 0 4
-1 4 0
3
1 3
3 2
1 2
# Entrée Sortie
1 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!