Max's Anger Contest Series 1 P4 - Greedily Gamboling

Points: 12 (partial)

Time limit: 2.0s

Java 3.0s

Memory limit: 1G

Author:

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$ $N$ vertices with $M$ $M$ bidirectional-weighted edges and $K$ $K$ toggles for the bits for any given edge weight you travel, find the shortest path from $1$ $1$ to $N$ $N$ .

The $i^\text{th}$ $i^{th}$ toggle allows you to set the $p_i^\text{th}$ $p_{i}^{th}$ bit to $0$ $0$ at most once on any edge weight you travel on from $1$ $1$ to $N$ $N$ .

You can use multiple toggles on the same edge.

What is the minimum cost to travel from $1$ $1$ to $N$ $N$ using at most $K$ $K$ of the toggles?

Constraints

$1 \le N \le 20\,000$ $1 \leq N \leq 20 000$

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

$0 \le K \le 5$ $0 \leq K \leq 5$

$0 \le p_i \le 10$ $0 \leq p_{i} \leq 10$

$1 \le u_i, v_i \le N$ $1 \leq u_{i}, v_{i} \leq N$

$u_i \ne v_i$ $u_{i} \neq v_{i}$

$1 \le w_i \le 40\,000$ $1 \leq w_{i} \leq 40 000$

The data are generated such that there is always a path of edges from $1$ $1$ to $N$ $N$ .

Subtask 1 [30%]

$K = 0$ $K = 0$

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line will contain three integers, $N$ $N$ , $M$ $M$ , and $K$ $K$ , the number of vertices, edges, and toggles, respectively.

The next $K$ $K$ lines will contain an integer, $p_i$ $p_{i}$ , the $i^\text{th}$ $i^{th}$ toggle that can be used to set the $p_i^\text{th}$ $p_{i}^{th}$ bit of any edge weight that is travelled on from $1$ $1$ to $N$ $N$ to $0$ $0$ .

The next $M$ $M$ lines will contain three integers, $u_i$ $u_{i}$ , $v_i$ $v_{i}$ , and $w_i$ $w_{i}$ , a bidirectional edge from $u_i$ $u_{i}$ to $v_i$ $v_{i}$ with a weight of $w_i$ $w_{i}$ .

Output Specification

Output the minimum distance from $1$ $1$ to $N$ $N$ after using at most $K$ $K$ of the toggles.

Sample Input

Copy

Sample Output

Copy

Explanation for Sample

It is optimal to take the path $1 \to 2 \to 3$ $1 \to 2 \to 3$ to get a distance of $0$ $0$ : use $p_1 = 1$ $p_{1} = 1$ on the edge from $1$ $1$ to $2$ $2$ , giving a weight of $0$ $0$ ; use $p_2 = 2$ $p_{2} = 2$ on the edge from $2$ $2$ to $3$ $3$ , giving a weight of $8$ $8$ ; use $p_3 = 3$ $p_{3} = 3$ on the edge from $2$ $2$ to $3$ $3$ again, giving a weight of $0$ $0$ .

Comments

0

vichua2006 commented on Jan. 2, 2023, 4:20 p.m.

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

1
maxcruickshanks commented on Jan. 4, 2023, 5:28 p.m. ← edited →
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:

Copy
3 3 3 3 10 3 2 1 17700 3 1 11327 3 2 28364

If you want further help debugging, I recommend joining the DMOJ Discord and using the help forum.

0

vichua2006 commented on Jan. 8, 2023, 7:28 p.m.

got it, thanks.