topcoder marathon match 109

This was hard and interesting problem, kind of Steiner forest problem with additional constraint on edge weight sum.

From this paper (https://arxiv.org/abs/1412.7693) I've created steiner tree via greedy approach ignoring constraint on edge sum. Then I fixed each route path by dijkstra on steiner tree.

Then by randomly adding/removing route I found a subset of routes satisfying constraint and which has max score.

I tried to make moves from this paper (https://arxiv.org/abs/1707.02753) but it didn't help much.