Subtask 1

It suffices to run Dijkstra's algorithm from ~1~ to ~N~.

Time Complexity: ~\mathcal{O}(M \log(N))~

Subtask 2

Realize that since toggles can only be used once, states of what toggles have been used can be represented with a bitmask.

Now, for each node and the current bitmask, consider all edges that connect this node and bitmask through all supersets of the current bitmask: if the current bit is on in the superset but not for the original bitmask and the current edge weight has that bit on, subtract it from the current weight. Once all bits are considered, push that node and new bitmask into the priority queue.

Finally, output the shortest distance from ~1~ to ~N~ using none, some, or all of the toggles.

Time Complexity: ~\mathcal{O}(MK (4^K + 3^K \log(N 3^K)))~

Note that it is possible to achieve ~\mathcal{O}(MK 3^K \log(N 3^K))~ by iterating only over the bitmasks that are supersets of the current bitmask without considering any extra masks.

Exercise

Consider how you could optimize the full solution to have a smaller power by reducing the base for the number of edges.

Implement and submit to this harder version with increased constraints on ~K~.