1.13. Длинный путь в графе

Заданы N-вершинный ориентированный граф с двумя выделенными вершинами v1 и v2 и целое число C. Требуется:

1. Определить, существует ли в заданном графе путь из вершины v1 в вершину v2, состоящий из C ребер (путь может иметь самопересечения как по вершинам, так и по ребрам).

2. Найти минимум функции | X  C |, где X — количество ребер в некотором пути из v1 в v2.

Входные данные

Первая строка входного файла содержит целое число N — количество вершин в графе (1£N£10). В следующих N строках расположена матрица N´N из нулей и единиц, элемент (ij) которой равен единице, если в графе есть ребро из вершины i в вершину j, и нулю, если такого ребра нет. (Граф может содержать петли, т.е. ребра, идущие из вершины в саму себя.) Элементы матрицы во входном файле записаны без разделительных пробелов.

 Наконец, строка N+2 содержит номера вершин v1 и v2, а строка N+3 — десятичную запись числа C (1£C<1050).

Выходные данные

В первую строку выходного файла выведите ответ на первый пункт задачи: «Yes», если путь длины C существует, и «No», если нет. Во вторую строку запишите ответ на второй пункт задачи. Если ни одного пути из v1 в v2 не существует, ваша программа должна вывести -1.

Пример входного файла

3

010

001

100

1 1

555555555555555555555555555555555

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

Yes

0

Вернуться к главе 1


Valid CSS! Valid XHTML 1.0!
Webmaster: Антон Лапунов
Используются технологии uCoz