Editorial for VMSS '15 #4 - Frank and Roads - Olympiads Online Judge

Editorial for VMSS '15 #4 - Frank and Roads

Remember to use this editorial 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.

Author: kobortor

We can represent the city Frank and Jeffrey lives in by using something called an adjacency list. The basic idea is an array of $N$ $N$ lists, vectors or other resizable data structures. The $i^\text{th}$ $i^{th}$ list will contain all the roads going out of the $i^\text{th}$ $i^{th}$ building. For example, if there was a road between building $3$ $3$ to $5$ $5$ and $3$ $3$ to $7$ $7$ , the $3^\text{rd}$ $3^{rd}$ list would contain $\{5, 7\}$ ${5, 7}$ . How to store the length of each road is left as an exercise to the reader.

Now after you're done implementing the adjacency list, we will use the popular Dijkstra's shortest path algorithm. The algorithm is very well explained on Wikipedia and many YouTube videos, probably better than I will ever explain it, so I will just link them here.

Once you understand the algorithm, we can start by initiating the algorithm at the $0^\text{th}$ $0^{th}$ building (where Frank starts). After the algorithm is finished running, we should have all the shortest distances from building $0$ $0$ to all the other buildings. To finish stuff off, we can simply check through each Food Basics and count how many can be reached in no more than $T$ $T$ km.

Final Complexity: $\mathcal O(M + N \log N)$ $O (M + N \log N)$

Comments

There are no comments at the moment.