Сверхбыстрый поезд

Автор задачи и разработчик: Даниил Васильев

Построим граф, где вершины являются городами, а рёбра являются железными дорогами. Заметим, что ответ всегда $$$0$$$ или $$$1$$$, так как мы можем построить простой путь от $$$1$$$ до $$$n$$$, где каждое нечётное ребро берём со знаком '+', а каждое чётное со знаком '-'.

Далее, граф может быть одного из двух видов:

  1. Граф не содержит циклов нечётной длины. Тогда граф двудольный. Пусть вершина $$$1$$$ находится в первой доле (если нет, меняем доли местами). Заметим, что из-за этого текущее время всегда чётно в первой доле и нечётно во второй доле. Тогда здесь также будет работать простой путь, так как чётность его рёбер равна чётности ответа.
  2. Граф содержит цикл нечётной длины. Тогда мы проверяем, какой ответ выдаст простой путь. Если он выдаст ответ $$$1$$$, то мы можем его улучшить, дойдя до цикла нечётной длины, пройдя его полностью с суммарным временем $$$-1$$$, и вернувшись назад на простой путь. В результате время уменьшается до $$$0$$$, что является наиболее оптимальным вариантом.

Итого, определяем, есть ли в графе цикл нечётной длины, и обрабатываем соответствующий случай, что занимает $$$O(n + m)$$$.