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