struggling with this question from an exam:
input:
DAG G=(V,E). each edge $e_i$ has weight $w_i\in \text{{0,1,2,3}} $
Two vertices : s,t
Number: k
output:
A path from s to t with total cost k (if exists)
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communitystruggling with this question from an exam:
input:
DAG G=(V,E). each edge $e_i$ has weight $w_i\in \text{{0,1,2,3}} $
Two vertices : s,t
Number: k
output:
A path from s to t with total cost k (if exists)
When you get a question about a DAG, the first thing to do is a topological sort.
Now, go through all vertexes in order. For each vertex $v$, keep all the possible costs of a path from $s$ to $v$; there will be no more than $3V$ distinct costs. For each edge $e(v,u)$, add to $u$ the costs of $v$ + the weight of $e$.