Interstellar Pathfinding

Problem Statement

There are n galaxies in the universe, each with an energy value e_i. There are m bidirectional wormholes connecting galaxies u and v. Using a wormhole from u to v consumes energy c and provides an energy gain of d (if current energy is less than c, the wormhole cannot be used). Find the minimum initial energy E0 required to travel from galaxy S to galaxy T such that the traveler arrives with non-negative energy. If it's impossible to reach T, output -1.

Input Format

First line contains four integers: n, m, S, T.

Second line contains n integers, where the i-th integer is e_i.

Next m lines each contain four integers: u, v, c, d.

Output Format

The minimum initial energy E0, or -1 if impossible.

Sample Input #1

4 4 1 4
10 5 8 3
1 2 4 3
2 3 2 1
3 4 5 0
1 4 9 0

Sample Output #1

7

Constraints

• 30% data: n ≤ 10, acyclic bidirectional wormholes
• 60% data: n ≤ 50, e_i ≤ 10^4
• 100% data: 1 ≤ n ≤ 200, 1 ≤ m ≤ 5*10^4, 1 ≤ e_i ≤ 10^9, 1 ≤ c ≤ 10^9, 1 ≤ d ≤ 10^9

Macau Travel Planner

Problem Background

A traveler is planning a trip to Macau but needs help optimizing their itinerary due to limited energy and various events that affect their journey.

Problem Statement

For each test case, given three integers N (locations), M (initial energy), and Q (bad events). Each location has an operation type:

• When op=1: The location is an attraction, which increases knowledge by l and decreases energy by t.
• When op=2: The location is a rest area, which restores energy by t (up to M).

Each location is followed by coordinates (x,y). The traveler encounters Q bad events at specific times and locations. Each bad event reduces knowledge by l when encountered. Movement between locations follows straight-line Euclidean distance (rounded). The traveler moves at a speed of 1 unit per time unit, consuming 1 energy per unit distance. Each location can be visited at most once. The goal is to maximize knowledge gained while returning to the origin without running out of energy.

Input Format

First line: T (number of test cases).

For each test case:

• First line: N, M, Q
• Next N lines: op_i and corresponding parameters
• Next Q lines: t_i, x_i, y_i (time and location of bad events)

Output Format

T lines, each containing the maximum knowledge achievable for the corresponding test case.

Sample Input #1

1
3 20 1
1 10 3 1 1
2 5 4 5
1 8 2 6 6
3 6 6

Sample Output #1

10

Sample Input #2

1
4 30 2
1 15 4 2 2
2 8 5 6
1 12 3 8 4
1 10 5 3 7
4 5 6
7 3 7

Sample Output #2

25

Sample Explanation #1

Location Information:

• Location 1: Attraction, +10 knowledge, -3 energy, coordinates (1,1)
• Location 2: Rest area, +5 energy, coordinates (4,5)
• Location 3: Attraction, +8 knowledge, -2 energy, coordinates (6,6)
• Bad event: Time 3, location (6,6)

Distance Calculation (rounded):

• Origin (0,0) to (1,1): √(1² + 1²) = √2 ≈ 1.41 → 1
• (1,1) to (4,5): √(3² + 4²) = 5 → 5
• (4,5) to (6,6): √(2² + 1²) = √5 ≈ 2.24 → 2
• (6,6) to origin: √(6² + 6²) = √72 ≈ 8.49 → 8

Optimal Path: Origin → Location 1 → Return to origin

• Outbound: Distance 1 + Attraction cost 3 = 4 energy
• Return: Distance 1 = 1 energy
• Total consumption: 5 energy < 20 energy
• Knowledge gained: 10

Sample Explanation #2

Location Information:

• Location 1: Attraction, +15 knowledge, -4 energy, coordinates (2,2)
• Location 2: Rest area, +8 energy, coordinates (5,6)
• Location 3: Attraction, +12 knowledge, -3 energy, coordinates (8,4)
• Location 4: Attraction, +10 knowledge, -5 energy, coordinates (3,7)
• Bad event 1: Time 4, location (5,6)
• Bad event 2: Time 7, location (3,7)

Optimal Path: Origin → Location 1 → Location 2 → Location 3 → Return to origin

Distance Calculation:

• Origin → (2,2): √(2² + 2²) = √8 ≈ 2.83 → 3
• (2,2) → (5,6): √(3² + 4²) = 5 → 5
• (5,6) → (8,4): √(3² + 2²) = √13 ≈ 3.61 → 4
• (8,4) → Origin: √(8² + 4²) = √80 ≈ 8.94 → 9

Energy Consumption Calculation:

• Movement cost: 3 + 5 + 4 + 9 = 21 energy
• Attraction cost: 4 + 3 = 7 energy
• Rest recovery: +8 energy
• Net consumption: 21 + 7 - 8 = 20 energy < 30 energy

Knowledge gained: 15 + 12 = 27 points

Bad event avoidance: Proper scheduling avoids bad events

Final output 25: In optimal path planning, some knowledge is lost to avoid bad events, resulting in 25 points gained.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N, Q ≤ 3 × 10^5
• -10^18 ≤ l, t, M ≤ 10^18
• -10^9 ≤ x, y, x_i, y_i ≤ 10^9