For the first subtask, we note that there is either one route or no routes from node 1 to any other node. Thus, we can keep track of the cost and the length of the path from node 1 to every other node, if such a path exists. For each query, we simply add the length*cost change to the initial cost to reach the node.

Time complexity: ~\mathcal{O}(N+D)~

For the second subtask, we run a single source shortest path algorithm, such as the priority queue version of Dijkstra's algorithm, for every single query. We modify the graph such that each node is split into ~\mathcal{O}(N)~ nodes. The ~i^{th}~ new node signifies reaching the original node in ~i~ edges. Because each node is split, the edges also need to be split as well.

Time complexity: ~\mathcal{O}(DNM \log (NM))~

For the third subtask, we run a single source shortest path algorithm that can handle negative edges weights, such as the Bellman-Ford Algorithm, for every single query. We use a similar graph modification as presented in the solution for the second subtask.

Time complexity: ~\mathcal{O}(DN^3M)~

For the fourth subtask, we want to keep track of the minimal cost to reach a node ~n~ using ~e~ edges. The easiest way to do this is as follows:

Since the problem guarantees that there are no cycles in the graph, we use a dynamic programming approach on the directed acyclic graph. Obviously, the cost to node 1 using 0 edges is ~0~.

We can reverse direction of each edge and perform a DFS on the graph on any remaining unvisited nodes. When we visit a node, we run DFS on its unvisited neighbors. Afterward, for each neighbor and ~e~, dist[cur_node][e] = min(dist[cur_node][e],dist[neighbor][e-1]+edge_cost).

To answer the queries, we simply iterate through dist[d] for each query.

Time complexity: ~\mathcal{O}(NM + DN)~

For the fifth subtask, we perform the same DFS procedure as in subtask 4 in order to obtain the minimum cost required to reach node ~n~ using ~e~ edges. In order to improve our algorithm, we improve the running time of the queries.

For each of the nodes, we can represent the cost of reaching node ~n~ using ~e~ edges with a toll change of ~c~ using linear equations in the form of ~y = ec + dist[n][e]~.

Now, we use a technique called the convex hull trick. We preprocess the linear equations of each node so that we can answer queries by performing a binary search on the linear equations present in the hull.

Time complexity: ~\mathcal{O}(NM + D \log N)~