I'm struggling with following problem: We have n < 37 cities and m < n * (n - 1) / 2 undirected roads between them. Every city has a treasure in it with g[i] gold. Our robbers wants to get from city 0 to city n - 1 and take as much gold as they can with them.
To do this, they can (or not) rob every city they visit. They're hurry, so they can visit only cities that land on the shortest path from city 0 to n - 1 (if there are more than one shortest path, they can choose freely).
But there is a catch — they also need to go back from city n - 1 to 0 (now, they can move as they want), but! they cannot visit any city they robbed twice (dwellers will wait for them).
How much gold can they rob on they way to city n - 1?