If you use topological sort, and then use dp, you should check that there is a way from s to vertex from which you want to get to the next vertex.