Spoilers and explanation of solution:
Each vertex here is one intersection in our hike. We don't actually care about the parts in-between, because there's only one way to go. The above is a visualisation of the final path, the red edges are the edges taken. Our graph looks "like that" because it's a hiking trail, not a maze, so there's no dead ends. This took about 2 seconds to generate, due to all the cloning needed to keep track of paths. The two veeery long edges on the ends are pretty obvious choices, but one might notice that pretty much every vertex takes the two maximum paths it has, given the restrictions of the path. There's still some mildly surprising paths, such as (99, 29) -> (89, 37) with a weight of 38. I'm wondering if there's a way to dismiss more paths... This graph is actually pretty free in terms of movement.
My actual solution takes ~150 ms to run (and 8 microseconds for part one with barely any optimization, damnn)
I've been working on a graph, messed something up, hopefully have this solved soon...