|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 07-3. Флойд - существование.
| Имя входного файла | input.txt |
| Имя выходного файла | output.txt |
| Максимальное время работы на одном тесте: | 5 секунд |
Дан ориентированный взвешенный граф. По его матрице смежности нужно для каждой пары вершин определить, существует кратчайший путь между ними или нет.
Комментарий:
Кратчайший путь может не существовать по двум причинам:
- Нет ни одного пути
- Есть путь сколь угодно маленького веса
Формат входных данных
В первой строке входного файла записано
единственное число N (1 <= N <= 100) -
количество вершин графа. В следующих N строках по N чисел -
матрица смежности графа (j-ое число в i-ой строке соответствует
весу ребра из вершины i в вершину j), в которой число 0 обозначает
отсутствие ребра, а любое другое число - наличие
ребра соответствующего веса. Все числа по модулю
не превышают 100.
Формат выходных данных
Выведите N строк по N чисел: j-ое число в i-ой строке
должно быть равно 0, если путь из i в j не существует,
1 - если существует кратчайший путь, и 2 - если существует
путь сколь угодно маленького веса.
Пример
| input.txt | output.txt |
5 0 1 2 0 0 1 0 3 0 0 2 3 0 0 0 0 0 0 0 -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 |