I wanted to add a series of quick solution sketches to my problems without one. These aren't technically full editorials, but I hope that they are enough for you if you are stuck. :-)

The first subtask was meant to reward dynamic programming approaches.

The second subtask was solvable with simple matrix exponentiation across a tropical semiring.

For the final subtask, if ~G~ is the matrix representing the graph, we precompute ~G^2, G^4, \dots, G^{2^p}~ and multiply an initial vector state (which represents the state after taking zero edges from the starting node) by the matrices to compute ~G^k v~ instead of finding ~G^k~ directly.