To celebrate being able to reconstruct his array, Max has decided to solve Single Source Shortest Path but wants it to be harder, so he came up with the following problem:
Given a graph of 
~N~ vertices with 
~M~ bidirectional-weighted edges and 
~K~ toggles for the bits for any given edge weight you travel, find the shortest path from 
~1~ to ~N~.
The 
~i^\text{th}~ toggle allows you to set the 
~p_i^\text{th}~ bit to 
~0~ at most once on any edge weight you travel on from ~1~ to ~N~.
You can use multiple toggles on the same edge.
What is the minimum cost to travel from ~1~ to ~N~ using at most ~K~ of the toggles?
Constraints
~1 \le N \le 20\,000~
~N-1 \le M \le \min(50\,000, \frac{N \times (N-1)}{2})~
~0 \le K \le 5~
~0 \le p_i \le 10~
~1 \le u_i, v_i \le N~
~u_i \ne v_i~
~1 \le w_i \le 40\,000~
The data are generated such that there is always a path of edges from ~1~ to ~N~.
Subtask 1 [30%]
~K = 0~
Subtask 2 [70%]
No additional constraints.
Input Specification
The first line will contain three integers, ~N~, ~M~, and ~K~, the number of vertices, edges, and toggles, respectively.
The next ~K~ lines will contain an integer, 
~p_i~, the ~i^\text{th}~ toggle that can be used to set the ~p_i^\text{th}~ bit of any edge weight that is travelled on from ~1~ to ~N~ to ~0~.
The next ~M~ lines will contain three integers, 
~u_i~, 
~v_i~, and 
~w_i~, a bidirectional edge from ~u_i~ to ~v_i~ with a weight of ~w_i~.
Output Specification
Output the minimum distance from ~1~ to ~N~ after using at most ~K~ of the toggles.
Sample Input
3 3 3
1
2
3
1 3 1
1 2 2
2 3 12
Sample Output
0
Explanation for Sample
It is optimal to take the path 
~1 \to 2 \to 3~ to get a distance of ~0~: use 
~p_1 = 1~ on the edge from ~1~ to 
~2~, giving a weight of ~0~; use 
~p_2 = 2~ on the edge from ~2~ to 
~3~, giving a weight of 
~8~; use 
~p_3 = 3~ on the edge from ~2~ to ~3~ again, giving a weight of ~0~.
Comments
Can someone take a look at my submission? I am fairly certain that I have the correct overall solution, but must have made a mistake in implementing it. link: https://dmoj.ca/submission/5177712
You are using a toggle for the same bit on the same edge multiple times (a bit can be toggled at most once for one edge).
Consider this test case:
If you want further help debugging, I recommend joining the DMOJ Discord and using the help forum.
got it, thanks.