We model the problem as a directed graph.

The first two subtasks can be solved by iterating over all paths of length ~k~, and storing the shortest distance between every pair of nodes. The time complexity is ~\mathcal O(n^k+q)~.

To fully solve the problem we use dynamic programming. Let ~dp[d][x][y]~ denote the length of the shortest path between ~x~ and ~y~ which uses at most ~d~ edges, and let ~w[x][y]~ be the length of the (shortest) edge between ~x~ and ~y~, or ~\infty~ if no such edge exists.

In the beginning, we initialize all the paths of length zero: ~dp[0][x][x] = 0~ and ~dp[0][x][y] = \infty~ for ~x \ne y~. When making a transition from ~d~ to ~d+1~, for each pair of nodes ~(x, y)~, we try to go from ~x~ to some node ~z~ using at most ~d~ edges, and from ~z~ to ~y~ using just one edge:

$$\displaystyle dp[d+1][x][y] = \min_z dp[d][x][z]+w[z][y]$$

The complexity is ~\mathcal O(kn^3+q)~, which solves the third subtask.

Notice that the shortest path between two nodes cannot use more than ~n-1~ edges (otherwise we would visit some node twice, i.e. we would have a cycle which could be removed to obtain a shorter path). Therefore, if ~k > n-1~, we can set ~k = n-1~ and the answer will be the same.