The following problem (I’m paraphrasing) appeared in the 2019 Balkan Olympiad in Informatics:
Five friends are on a road trip in a country with $N$ cities and $M$ bidirectional roads joining them. They start in city $1$ and wish to end in city $N$.
All of them love driving, so they move in the following fashion:
- Each day, they start in the city they ended at the previous day (city $1$ on the first day) and follow a path consisting of exactly five roads (i.e. they visit six cities and the first visited city is the last visited city of the previous day).
- They may visit a city multiple times across multiple days, but they may not visit a city multiple times in the same day.
- They can’t stop in the middle of the path: if they visit city $N$ after using $k < 5$ roads on some day, they can’t end their trip.
Find the shortest path needed to complete this road trip, or determine that it isn’t possible. In the case that there are multiple shortest paths, find the lexographically smallest one when looking at only the sequence formed by the ($5k+1$)-th cities visited on the path (i.e. city $1$, …, city $N$)
$N leq 10^5$ and $M leq 5 cdot 10^5$.
The official problem statement can be found on the contest website (day 2 problem 2).
I haven’t been able to find an efficient solution to this problem (from both asking others and searching online), and nobody solved it in the contest. I currently have no idea how to even approach it.
Is there an efficient algorithm to solve this problem, perhaps even for $k$ friends instead of five friends? Since $N$ and $M$ are so large, the algorithm should be linear or linearithmic.