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?
Constraints
The data are generated such that there is always a path of edges from to
.
Note the increased constraints on .
Input Specification
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 Specification
Output the minimum distance from to
after using at most
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 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
.
Comments