First impression is to use HC/SA , but evaluation is too slow.

Straightforward score calculation would be \(N*M*logN*D\).

If we only consider changing one road to different day, it would only affect 2 days, so we can drop \(*D\) part.

Instead of using dijkstra we can use bellman-ford with edges sorted from the root, which runs in almost linear time (needs 2-3 iterations on most graphs, a bit more on more complex ones), so we get evaluation in \(N*M\) which is still too slow.

Since we only change one edge in each graph, we don’t have to run bellman-ford from scratch, instead we can only update affected area. This reduces runtime by large constant \(B\).

We can sacrifice some evaluation accuracy for more speed - instead of calculating distances for all pairs, pick some sample of \(C=20\) starting nodes (chosen on the boundary of circle to include longest paths), now we have cost down to \(C*M/B\) which can run a few hundred thousand iterations and at this point SA becomes viable.

If this is implemented with decent optimizations around 47B provisional score should be achieved.

For some extra points we can replace SA with SA + HC, where last stage HC runs on growing node sample with full graph in the end.

Another idea is based on edge synergies: for each pair of edges we can calculate how much score is saved if both are removed as opposed of each being removed separately. Doing this for every pair is too slow, but it is good enough to consider only neighbors. Geometrically edge pairs with best synergy are usually almost collinear. If we prioritize creating such pairs, we get decent score boost, reaching high 48B.