A fintech company runs a mainframe integration gateway that routes requests between legacy services. Each directed integration link has a cost (latency + compute) and a cooldown rule: once you use a specific directed link, you must wait a minimum number of hops before you can use that same directed link again. Violating cooldowns can trigger rate-limit bans and failed settlements.
You are given a directed graph with n services labeled 0..n-1. Each edge is represented as [u, v, cost, minGap]:
u -> v is a directed linkcost >= 0 is the cost to traverse itminGap >= 0 means after using this exact directed edge, you may use it again only after at least minGap other edges have been traversed in between.You must route from src to dst using exactly k hops (i.e., traverse exactly k edges). Return the minimum total cost among all valid routes, or -1 if impossible.
If a directed edge e was last used on hop t (1-indexed), it can next be used on hop t' only if:
t' - t > minGap (equivalently t' >= t + minGap + 1)Example 1
n = 4, edges = [[0,1,2,1],[1,2,2,0],[2,3,2,0],[1,1,1,2]], src = 0, dst = 3, k = 360->1->2->3 (3 hops). No edge is reused, so cooldowns are satisfied. Total cost = 2+2+2=6.Example 2
n = 3, edges = [[0,1,1,2],[1,0,1,2],[1,2,1,0]], src = 0, dst = 2, k = 3-10->1 or 1->0 too soon (they have minGap=2). So no valid 3-hop route reaches 2.(u,v) are still distinct if both appear).src == dst, you still must take exactly k hops; returning 0 is only valid when k == 0.1 <= n <= 500 <= len(edges) <= 2000 <= cost <= 10^60 <= minGap <= 100 <= k <= 50