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

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

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

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

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

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

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

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

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

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

3

010

001

100

1 1

555555555555555555555555555555555

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

Yes

0

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

Webmaster: Антон Лапунов