Count probe routes
Your task
A network team counts the diagnostic routes a probe could take. link_ms is a square table where link_ms[a][b] is the one way latency in milliseconds of the link from node a to node b, and 0 means there is no link, including every entry on the diagonal. The table is not always symmetric. A route starts at node 0, ends at the last node, never visits a node twice, totals at most budget milliseconds, and passes through every node listed in must_visit. must_visit may repeat a node and may name the start or the end. Return how many such routes exist. Return 0 when the table has no nodes. A table with a single node gives one route, the one that has already arrived, whenever budget is not negative. There are at most 12 nodes.
Examples
count_relay_routes(link_ms: list[list[int]], budget: int, must_visit: list[int]) -> intExample 1
Input
count_relay_routes([[0, 4, 9], [4, 0, 3], [9, 3, 0]], 12, [])Output
2Example 2
Input
count_relay_routes([[0, 4, 9], [4, 0, 3], [9, 3, 0]], 12, [1])Output
1Example 3
Input
count_relay_routes([[0, 4, 9], [4, 0, 3], [9, 3, 0]], 6, [])Output
0