You're given a directed graph G with N vertices and M edges. Each edge weight w is a linear function of time, i.e. at + b for some given values of a and b. You're also given a time interval [t1, t2].
Find the minimum spanning tree in the time interval [t1, t2], i.e. the time instant t and the edges that make up the minimum spanning tree.
Extension 1 (better complexity solution possible?):
Extension 2 (higher degree polynomials)
Hope you enjoyed the puzzle!