АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

784. Флойд-существование

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

 
Задача "Флойд-существование"

Дан ориентированный взвешенный граф. 
По его матрице смежности нужно для каждой пары
вершин определить, существует ли кратчайший путь
между ними или нет.

Комментарий:
Кратчайший путь может не существовать по двум причинам:
-Нет ни одного пути
-Есть пути сколь угодно маленького веса

Входные данные:
В первой строке входного файла записано 
единственное число: N (1 <= N <= 100) - 
количество вершин графа. В следующих N строках по N чисел - 
матрица смежности графа (j-ое число в i-ой строке соответствует
весу ребра из вершины i в вершину j): число 0 обозначает
отсутствие ребра, а любое другое число - наличие
ребра соответствующего веса. Все числа по модулю
не превышают 100. 

Выходные данные:
Выведите N строк по N чисел. j-ое число в i-ой строке должно 
соответствовать кратчайшему пути из вершины i в вершину j.
Число должно быть равно 0, если пути не существует,
1 - если существует кратчайший путь, и 2 - если пути существуют,
но бывают пути сколь угодно маленького веса.

Пример входного файла
5
0 1 2 0 0
1 0 3 0 0
2 3 0 0 0
0 0 0 4 -1
0 0 0 -1 0 

Пример выходного файла
1 1 1 0 0
1 1 1 0 0
1 1 1 0 0
0 0 0 2 2
0 0 0 2 2

Статистика Послать на проверку Обсуждение задачи Автор/источник: olympiads.ru
Учебные курсы / Задачи с olympiads.ru /
783. 259 - Флойд-макс 784. 785. 261 - Путь-2 786. 262 - Форд-Беллман 787. 263 - Лабиринт знаний
 
время генерации 0.094 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.