A version I was told to think about was competing travel agents. At each step they need to find a better solution or know when to stop looking. It's still not quite there "given the [graph and] costs and a number x, decide whether there is a round-trip route cheaper than x" but if you are handed a graph you can say it's shorter and then give it as the answer. The difference is there may be approaches that prove there is a shorter path, without finding it.
However, the mental model is vary close to the generic solution because someone can hand you the 2nd best solution which looks nothing like the best solution and you still need to find it. Where if you are handed the best solution they may be a shortcut to proving it's the best.
PS: The Clique problem always seemed like the version where shortcuts seemed most obvious. But, understanding why they fail is a larger mental jump IMO than NP Hard TSP to NP Complete TSP.
However, the mental model is vary close to the generic solution because someone can hand you the 2nd best solution which looks nothing like the best solution and you still need to find it. Where if you are handed the best solution they may be a shortcut to proving it's the best.
PS: The Clique problem always seemed like the version where shortcuts seemed most obvious. But, understanding why they fail is a larger mental jump IMO than NP Hard TSP to NP Complete TSP.