27

Question: Given a weighted DAG, find a path from 1 to N with maximum number of nodes such that the weight of the path is less than T. Given: -> At least one such path exists -> There is at most one edge between any pair of nodes -> N <= 1e3 Solution: Find a topological sort of the graph Notice that all nodes between 1 and N in the topological sort are the only nodes that could possibly be on any path from 1 to N. So, for each node I, update the cost of reaching each of its neighbours J Also maintain and update the number of nodes to reach each node Array P contains a topological ordering of the DAG Z is the size of P edge[src][dst] denotes whether there is an edge from src to dst cost[src] denotes the cost of reaching src from node 1 weight[src][dst] is the weight of the edge from src to dst num[src] is the number of nodes in the path from 1 to src num[1] = 1 for (i=0; i<z; i++) { src = p[i]; for (j=i+1; j<z; j++) { dst = p[j]; if (!edge[src][dst]) continue; if (cost[src] + weight[src][dst] <= t && num[src] >= num[dst]) { cost[dst] = cost[src] + weight[src][dst]; num[dst] = num[src] + 1; } } }