Fibre to the Villages

A county lays fibre-optic cable along its roads. Junction 0 is the exchange; some junctions are villages that must be connected to it. Cable can only run along roads, and laying it along road (a, b, length) costs length. Signal quality sets a second rule: for every village, the shortest route along the laid cable from the exchange must be no longer than that village's limit.

Write lay_fibre(inst) that returns the list of road indices (positions in inst["roads"]) to lay cable on, with the smallest total length you can manage. Other junctions may be used as branching points.

inst is a dict:

• "points": the (x, y) of each junction (only for drawing; lengths come from the roads)
• "roads": a list of (a, b, length) triples, two-way, whole-number lengths
• "villages": the list of village junctions
• "limit": limit[i] is the longest allowed route for village villages[i]. In the tests it is one and a half times the village's shortest road distance from the exchange, rounded down.

The tests build their maps with fibre_map(n, k, seed) (n junctions, k villages). road_distances(n, roads, source) gives the shortest distance from source to every junction over a list of roads (None where unreachable), so road_distances(n, [roads[i] for i in chosen], 0) measures the routes along your cable. Both are available in your code.

How this problem is scored

The checker's own plan joins every village to the exchange by its shortest road route (at each junction the route comes from the neighbour that gives the shortest distance, the smaller junction number on a tie) and lays cable on all of those roads. Your plan passes if every village is connected within its limit and the total is no more than the checker's. Its quality (0 to 100) is the share of the gap between the checker's plan and the optimum (proved by an exact solver) that you close.

Examples

Input:  inst = {"points": [(0, 0), (40, 30), (100, 0), (80, 40), (50, 0), (90, 20)],
                "roads": [(0, 1, 7), (0, 4, 7), (1, 3, 3), (1, 4, 5),
                          (2, 4, 4), (2, 5, 2), (3, 5, 3), (4, 5, 7)],
                "villages": [3, 4, 5], "limit": [15, 10, 19]}
Output: [1, 2, 3, 6]   (7 + 3 + 5 + 3 = 18 of cable, the optimum)
Explanation: routes along the cable: village 4 is 7 away (0-4), village 3 is 15 (0-4-1-3)
             and village 5 is 18 (0-4-1-3-5), all within their limits. Junction 1 is a
             branching point. The shortest routes 0-1-3, 0-4 and 0-4-2-5 need 23 of cable.
             [1, 4, 5, 6] needs only 16, but then village 3's route is 0-4-2-5-3 = 16,
             over its limit of 15.

Input:  inst = fibre_map(60, 20, 2)
Output: any valid list of roads using no more cable than the shortest routes (4726 here)

Constraints

• 30 <= n <= 250 junctions, 10 <= k <= 60 villages, each junction on 2 to 7 roads
• Each test must finish in well under a second in your browser. Limit your loops by a number of rounds, not by the clock, so the result is the same on every run.

Goals

• Share cable between villages instead of giving each its own route
• Respect a limit on each village's route while sharing
• Combine shortest-path searches with greedy growth and a pruning pass