MOI Day 2, Problem 2 (Пресметување патарина): $$$\newline$$$ Link: https://mendo.mk/Task.do?id=996 $$$\newline$$$ Solution for 67 points: This approach was obvious, just run dijkstra from every node $$$i$$$ and maintain $$$dp[last][mask]$$$ as the minimum cost to reach node $$$last$$$ from $$$i$$$ while mask is the binary representation of the coupons u have already used up. However, time and memory consumption of this solution grows exponentially making it run in $$$\approx O(2^{k} \cdot n^2 + m \cdot n \cdot log(2^{k} \cdot n))$$$, where $$$k$$$ is the number of coupons, $$$m$$$ is the number of edges and $$$n$$$ is the number of nodes. This doesn't pass when $$$k\le 20$$$ and the graph is a clique as there are too many routes and coupons to be checked.$$$\newline$$$ Full Solution: The trick for the full solution is that we don't actually care about which coupons are used precisely, but how many edges were used on a path. If we know the number of edges on a path we can easily sort the edges in descending order and put the highest value coupons for the most expensive edges accordingly (as long as we have coupons to spend). It is not hard to see why this greedy works.
Now, let's define $$$f(x,y,z)$$$ as the minimum cost to travel from node $$$x$$$ to node $$$y$$$ using exactly $$$z$$$ edges. We can use floyd warshall's algorithm to compute the shortest path between any two nodes using any number of edges. However, we do need to note that the maximum number of edges used on a path can be at most $$$n - 1$$$, otherwise we would visit a node twice wasting turns and coupons for no reason. This sets the following constraints (assuming we index nodes from 0), $$$0\le x,y \le {n-1}$$$ and $$$1\le z \le n - 1$$$. We also define $$$path(x,y,z)$$$ as the edges sitting on the optimal path in the corresponding state. Consider state for some $$$(x,y,z)$$$, if $$$\exists$$$ $$$p$$$ that is a node on the path between $$$x$$$ and $$$y$$$, we can modify floyd warshall's algorithm in a way that we brute force $$$e1$$$ and $$$e2$$$, the number of edges on a path $$$(x,p)$$$ and the number of edges on a path $$$(p,y)$$$, respectively. Then we combine the paths, sort the edges in descending order and use the coupons greedily, if the answer is smaller than $$$f(x,y,z = e1 + e2)$$$ we update $$$path(x,y,z)$$$ and $$$f(x,y,z)$$$. The answer to the problem is:

$$$\newline$$$ Time Complexity $$$O(n^5)$$$ $$$\newline$$$ Implementation: https://pastebin.com/mQSWkVzr