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 lists, vectors or other resizable data structures. The list will contain all the roads going out of the building. For example, if there was a road between building to and to , the list would contain . 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 building (where Frank starts). After the algorithm is finished running, we should have all the shortest distances from building 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 km.

Final Complexity: