Украинские олимпиаы: Украинская олимпиада 2014

Как-то раз Лиса Симпсон, персонаж мультсериала «Симпсоны», оказалась в одной из вершин некоторого связного неориентированного графа. Лиса может передвигаться между соединенными ребром вершинами графа, однако, кроме вершины, в которой она на данный момент находится, а также всех смежных с ней вершин, девочке ничего не видно. К тому же у Лисы нет с собой ручки и бумаги, чтобы отмечать маршрут своих передвижений или другую информацию. Зато у нее есть неограниченное количество камешков, которые девочка может оставлять в вершинах графа, и именно этим она планирует воспользоваться, чтобы исследовать некоторые его свойства. К сожалению, в одной вершине графа помещается не больше чем 1000 камешков, но Лиса верит, что этого ей хватит. Известно, что количество вершин в графе не меньше 2 и не больше 500.

Данная задача состоит из двух подзадач:

1. В первой подзадаче ни в одной из вершин графа сначала нет камешков, а Лиса хочет выяснить, сколько вершин содержит граф.
2. Во второй подзадаче в одной из вершин графа (отличной от начальной) лежит один камешек, а в остальных вершинах — ни одного. Лиса хочет определить длину самого короткого пути по ребрам между начальной вершиной и той, где лежит камешек (длину каждого ребра считаем единичной).

Напишите функцию graph, которая по информации о количестве камешков в текущей вершине графа и всех смежных с ней вершинах определяет следующее действие Лисы: сколько камешков оставить в текущей вершине (или забрать из нее) и в какую из смежных вершин пойти дальше; или, когда Лиса готова назвать ответ на вопрос подзадачи, дает этот ответ.

Сдать эту задачу можно только на языке C++!

Вы должны послать файл, который содержит реализацию процедуры graph, детально описанную ниже, и, в случае надобности, другой код, который необходим для корректной работы этой процедуры, но не содержит самого тела программы (т. е. функции main в C++). При тестировании ваш файл будет дополнен специальным телом программы, написанным жюри. Тело соответствующим образом будет вызывать написанную вами процедуру и проверять корректность алгоритма, который она воплощает. Реализованная вами процедура должна иметь такой вид:

C++: void graph(int subproblem, int neighborsCount, int neighbors[], int & current, int & whereToGo, int & answer);

Смысл параметров:

1. subproblem — номер подзадачи: 1 для подзадачи определения количества вершин, 2 для подзадачи поиска длины самого короткого пути. Номер подзадачи не меняется при запусках процедуры на одном и том же графе.
2. neighborsCount — количество смежных вершин, т. е. количество вершин, соединенных с текущей вершиной ребром.
3. neighbors — массив, содержащий ровно neighborsCount элементов (индексация с нуля) — количества камешков в смежных вершинах. Обратите внимание, что порядок смежных вершин может быть разным (произвольным образом переставленным) во время разных вызовов процедуры, даже если текущая вершина одна и та же. Содержимое этого массива процедура в случае необходимости может менять, но на реальном количестве камешков в соответствующих вершинах это никак не отражается: Лиса может менять количество камешков исключительно в той вершине, где она на данный момент находится.
4. current — количество камешков в текущей вершине. Это количество в процедуре можно изменить (как увеличить, так и уменьшить, но так, чтобы количество не стало отрицательным или большим чем 1000). При этом изменится и реальное количество камешков в соответствующей вершине графа.
5. whereToGo — начальное значение этого параметра (аргумент, который передает тело программы) равно -1. Если Лиса продолжает исследование графа, это значение нужно переписать, сделав равным количеству камешков в следующей вершине, куда должна пойти Лиса (обратите внимание: это не индекс в массиве neighbors, а значение!). Если в массиве neighbors есть сразу несколько элементов с такими значениями, Лиса пойдет в одну из соответствующих вершин, но то, в какую именно, процедура ограничить не может. Если Лиса на данном вызове процедуры уже готова дать ответ, начальное значение -1 этого параметра переписывать не нужно (и нельзя).
6. answer — начальное значение этого параметра (аргумент, который передает тело программы) также равно -1. Если Лиса готова дать ответ, это значение следует переписать, сделав его равным ответу. Если Лиса на данном вызове процедуры еще не готова дать ответ, начальное значение -1 этого параметра переписывать не нужно (и нельзя).