LCC/Moose '20 Contest 3 S4 - Minimum Maximum Edge

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

You are given a connected undirected graph with N nodes and M edges, where each edge has a weight W_i and a value C_i. In one operation you can decrease the weight of some edge i by C_i, edge weights can be zero or negative. You are to perform at most K operations, and then choose some connected subgraph of the graph containing all N nodes (possibly the graph itself). Of all possible ways of doing so, you want to minimize the maximum edge weight of the connected subgraph.

Input Specification

The first line contains 3 integers N\ (1 \leq N \leq 10^5), M\ \left(N-1 \leq M \leq min\left(\frac{N(N-1)}{2},2\cdot 10^5\right)\right), and K\ (0 \leq K \leq 10^9).

The next M lines contain 4 integers A_i,\ B_i\ (1 \leq A_i,B_i \leq N, A_i \neq B_i),\ W_i\ (1 \leq W_i \leq 10^{18}),\ C_i\ (1 \leq C_i \leq 10^9), indicating an undirected edge between A_i and B_i with weight W_i and value C_i. There may be repeated edges.

Output Specification

On one line you are to print the minimum maximum edge weight of the connected subgraph.


Subtask 1 (10%)

K = 0

Subtask 2 (30%)

N \leq 15

Subtask 3 (60%)

No further constraints.

Sample Input

4 4 5
1 2 2 1
2 3 3 2
3 4 4 3
4 1 1 4

Sample Output



There are no comments at the moment.