Задача №221. Длинный путь в графе
Заданы N-вершинный ориентированный граф с двумя выделенными вершинами v1 и v2 и целое число C. Требуется:
1) определить, существует ли в заданном графе путь из вершины v1 в вершину v2, состоящий из C ребер (путь может иметь самопересечения как по вершинам, так и по ребрам);
2) найти минимум функции | X - C |, где X – количество ребер в некотором пути из v1 в v2 .
Первая строка входных данных содержит целое число N – количество вершин в графе (1 ≤ N ≤ 10). В следующих N строках расположена матрица N × N из нулей и единиц, элемент (i, j) которой равен единице, если в графе есть ребро из вершины i в вершину j, и нулю, если такого ребра нет. (Граф может содержать петли, т.е. ребра, идущие из вершины в саму себя). Элементы матрицы записаны без разделительных пробелов.
Наконец, строка N+2 содержит номера вершин v1 и v2 , а строка N+3 – десятичную запись числа C (1 ≤ C < 1050).
В первую строку выведите ответ на первый вопрос задачи: «Yes», если путь длины C существует, и «No», если нет. Во вторую строку запишите ответ на второй вопрос задачи. Если ни одного пути из v1 в v2 не существует, ваша программа должна вывести во второй строке-1.