For example, what happens if you skip \(100\) checkpoints?

In this case, you are imposed a penalty of \(2^{99} \approx 10^{30}\); however, even if you visit all the checkpoints, the total distance will be at most \(N \times 10^5\), so skipping this many checkpoints is obviously pointless.

Here, the following DP (Dynamic Programming) is effective:
dp[final checkpoint visited][the number of skipped checkpoints] = (minimum distance of the path).
Note that we only have to consider the second index being less than \(100\).

The DP table is initialized with \(\infty\), with an exception of \(dp[1][0]=0\); the answer is the minimum value among “\(dp[N][i]\) plus the penalty when \(i\) checkpoints are skipped.”

Therefore, the problem can be solved in a total of \(O(NC^2)\) time, where \(C\) is the maximum number of checkpoints to be skipped. (Using \(C=100\) may be a bit hard to fit in the time limit, but a better estimation yields a sufficiently small \(C\) to fit in the time limit with ease.)