Дан неориентированный взвешенный граф с отрицательными весами, необходимо выдавать информацию о кратчайшем пути между 2 вершинами.
Входные данные
В первой строчке дано целое число n
- количество вершин в графе. Дальше на вход подается матрица смежности, в которой -1
означает отсутствие ребра между вершинами. После матрицы идет число k
- количество запросов, в следующих k
строках содержится по 2 числа, a
и b
- вершины в запросе.
Выходные данные
В строке должно содержаться k
чисел - расстояние между парой чисел из запроса в порядке их ввода, если нельзя добраться из вершины a
в вершину b
, следует вывести Imp
.