$6.$ Bimsa is a young lioness whose evil uncle has just banished her from the land of Honor Stone, proclaiming: "Run away, Bimsa. Run away, and never return." Bimsa has knowledge of all landmarks and trails in and around Honor Stone. For each landmark, she knows its $\text{'}\backslash ($ x $\backslash )\text{'}$ and $\text{'}\backslash ($ y $\backslash )\text{'}$ coordinates and whether it is inside or outside of Honor Stone. For each trail, she knows its positive integer length and the two landmarks it directly connects. Each landmark connects to at most five trails, each trail may be traversed in either direction, and every landmark can be reached along trails from the gorge, the landmark where Bimsa is now. Bimsa wants to leave Honor Stone quickly, while only traversing trails in a way that never returns: traversing a trail from landmark $\text{'}\backslash ($ a $\backslash )\text{'}$ to landmark $\text{'}\backslash ($ b $\backslash )\text{'}$ never returns if the distance from $\text{'}\backslash ($ a $\backslash )\text{'}$ to the gorge is strictly smaller than the distance from $\text{'}$b$\text{'}$ to the gorge. If there are $\text{'}\backslash ($ n $\backslash )\text{'}$ landmarks in Honor Stone,

Page $1$ of $2$

describe an $\backslash (\backslash$mathrm$\{$O$\}(\backslash$mathrm$\{$n$\})\backslash )-$time algorithm to determine a shortest route that never returns, from the gorge to any landmark outside of Honor Stone. Explain why your alogorithm determines shortest route in $\backslash (\backslash$mathrm$\{$O$\}(\backslash$mathrm$\{$n$\})\backslash )$ complexity.

$[10][$CO$02,$ CO$03][$BTL $4]$