Is there a known algorithm that solves the following problem: Given a directed acyclic graph $G$ with weights on the edges, all nodes have a blue color. We seek to color with red every path $P$ with $K$ edges such that the sum of weights of this path is greater than a threshold (T)
We tried to use dynamic programming to solve this, P(s,t,K) is all the paths from s to t with K length, then we moved to k=1 until k=K and this way we find all paths between all nodes with exactly K length. then we go over these paths and check which paths sum exceed the threshold T and we color it with red. this algorithm is exponential. is there a better one?