Frogger's shortest trip

Shortest-path problem with custom movement costs

This is a hard coding problem that combines graph construction with shortest-path search. It asks you to model a frog's movement across stones as a weighted graph, where each stone is a node and the cost of each edge depends on the type of jump available.

The core challenge is understanding the two jump mechanics: a cheap fixed-cost "short hop" to a designated nearest neighbor, and a distance-based "long jump" to any stone. You must precompute the nearest neighbor for each stone according to a specific tiebreaking rule, then use Dijkstra's algorithm (or dynamic programming) to find the minimum cost for each query trip. The problem rewards careful implementation in C++ or Python, correct handling of edge cases (boundary stones, tie-breaking), and efficient shortest-path logic.

• Graph representation and edge weight assignment
• Precomputation of neighbor relationships
• Single-source shortest-path queries (Dijkstra)
• Managing multiple independent trip queries efficiently