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 vertices with bidirectional-weighted edges and toggles for the bits for any given edge weight you travel, find the shortest path from to .
The toggle allows you to set the bit to at most once on any edge weight you travel on from to .
You can use multiple toggles on the same edge.
What is the minimum cost to travel from to using at most of the toggles?
The data are generated such that there is always a path of edges from to .
Subtask 1 [30%]
Subtask 2 [70%]
No additional constraints.
The first line will contain three integers, , , and , the number of vertices, edges, and toggles, respectively.
The next lines will contain an integer, , the toggle that can be used to set the bit of any edge weight that is travelled on from to to .
The next lines will contain three integers, , , and , a bidirectional edge from to with a weight of .
Output the minimum distance from to after using at most of the toggles.
3 3 3 1 2 3 1 3 1 1 2 2 2 3 12
Explanation for Sample
It is optimal to take the path to get a distance of : use on the edge from to , giving a weight of ; use on the edge from to , giving a weight of ; use on the edge from to again, giving a weight of .
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.