Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 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

(с) Свиридов Ярослав


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: