## Editorial for UACC 1 P6 - Labyrinth Treasure

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Authors:

,Notice that the locked boxes form a directed graph. An edge from box to box means that box can be opened after obtaining a key from box . Since only one key is directly required to open any given box, we simply need to find the shortest path to the to box with the treasure. This can be computed using Dijkstra's algorithm once we have constructed the graph.

The weight of the edge from box to box is equal to the distance between the rooms that they are located in. All that is left is to compute these distances.

#### Subtask 1

It is sufficient to perform a BFS or DFS to find the distances.

#### Subtask 2

Since the rooms are arranged in a tree, we can compute distances using LCA. More specifically, we can root the tree arbitrarily and compute distances from the root to each node. Define as the distance from the root to node . The distance between two nodes and can be computed as .

## Comments