The solution to this hard problem is going to be on a simple version of this problem. In the simple version, there won't exist any roads of type ~3~, and the truck has to get empty to city ~N~ in the last step. In other words, it is allowed for the truck to pass through city ~N~ on its trip as many times as it likes, but in the last step when it enters city ~N~ it has to be empty.

The rest of this description is going to be devoted to the problem with these two restrictions, while the solution of the original problem will be left to the reader for exercise.

So, the new problem which we are about to solve says: how to get from city ~1~ to city ~N~ using at most ~K~ steps with the restriction that truck has to get into city ~N~ empty. As a solution, dynamic programming is used. Let ~dp[a][b][k]~ be the number of different ways to get from city ~a~ to city ~b~ using exactly ~k~ steps starting (from city ~a~) and ending (in city ~b~) with an empty truck. The first road which we have to pass in our trip will have to be road type ~1~ in which we load some kind of cargo. Let's mark this road as ~a \to x~. Then we choose the road on which we unload exactly that piece of cargo (which has to be a road of type ~2~). Let's mark this road as ~y \to z~. Then we can add to the solution all the paths, i.e. ~dp[x][y][k_1] \times dp[z][b][k_2]~ where ~k_1+k_2+2 = k~. Unfortunately, a solution implemented this way will have complexity ~\mathcal O(E^2 K^2)~ which is not enough to get all points for this task.

A better solution is to use an additional dynamic function ~dp2[a][b][k]~ which will contain the number of different trips from city ~a~ to ~b~ using exactly ~k~ steps while starting and ending with an empty truck (and never empty in the middle of the trip).

Dynamic tables are calculated increasingly by number ~k~. While calculating table ~dp~, we are finding the first town and step in which our truck is going to be empty. If it happens in city ~c~ in step ~k_1~, we have:

$$\displaystyle dp[a][b][k] \mathbin{+=} dp2[a][c][k_1] \times dp[c][b][k-k_1]$$

Parallel with that, we are calculating dynamic table ~dp2~. Let's search for roads ~a \to x~ and ~y \to z~ where we are loading and unloading the same type of cargo. We have:

$$\displaystyle dp2[a][b][k] \mathbin{+=} dp[x][y][k-2]$$

Complexity of this solution can be represented as ~\mathcal O(N^3 K^2 + E^2)~, which is enough to get all points for this task.