Task
Time limit:
1000 ms,
Memory limit:
32 Mb
Дан неориентированный взвешенный граф с отрицательными весами, необходимо выдавать информацию о кратчайшем пути между 2 вершинами.
Входные данные:
В первой строчке дано целое число n - количество вершин в графе.
Дальше на вход подается матрица смежности, в которой -1 означает отсутсвие ребра между вершинами.
После матрицы идет число k - количество запросов, в следующих k строках содержится по 2 числа а и b - вершины в запросе.
Выходные данные:
В строке должно содержаться k чисел - расстояние между парой чисел из запроса в порядке их ввода, если нельзя добраться из вершины a в вершину b, следует вывести Imp.
Пример:
|
Ввод |
Вывод |
|
3
0 3 -1
3 0 4
-1 4 0
3
1 3
3 2
1 2
|
7
4
3 |
(с) Свиридов Ярослав