Max's Anger Contest Series 1 P4 - Greedily Gamboling (Hard Version)

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 1G

Problem type

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?


1 \le N \le 20\,000

N - 1 \le M \le \min(50\,000, \frac{N \times (N - 1)}{2})

0 \le K \le 8

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.

Note the increased constraints on K.

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 3 1
1 2 2
2 3 12

Sample Output


Explanation for Sample

It is optimal to take the path 1 \rightarrow 2 \rightarrow 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.


There are no comments at the moment.