|
Yep, it's a graph search, It's also a subset of the traveling salesman problem...
Representation is important, I would consider and array of linked lists
Each element in the array represents all the roads leading out of that city.
This also falls under the domain of AI searching. You are not interested in the path cost per se, you are interested in picking a path that maximizes a certain value, specifically the maximum weight that can be driven over the roads traveled to reach that city.
The link list only represents path costs, you also need to create a graph class to deal with actually traveling down different routes.
I suggest you look up IDA*, it's ideal for this situation. H(N) in this case is the maximum weight value along this path. (normalized so that the fringe is sorted correctly)
It's deliciously neat so you could code this in a reasonable amount of time. Your allowed reference materials correct? You should definitely bring Artificial Intelligence A modern Approach - Second edition Stuart Russel and Peter Norvig.
This problem isn't solvable with plain BFS because the search space is way too big and you would have to search all of it to be sure you have the best possible solution.
Last time I went to a programming contest my group had a literal library with us for reference it helped us IMMENSELY.
__________________
"It better be funny" 
|