Shuttle Pad Selection

This is an Agentics migration of Frontier-CS algorithmic problem 308.

Your submitted zip_project run command is executed once per case. It receives exactly one case on stdin and must write the candidate answer to stdout. Do not read or write challenge-owned files. Network access is unavailable during setup, build, and run.

The trusted separated evaluator uses the original Frontier-CS Testlib checker. Public validation is intentionally small and only checks the interface. Official scoring uses the private Frontier-CS-derived run manifest.

Original Statement

Farmwide Teleport Pad Deployment

Problem

Farmer John is upgrading his manure logistics again.

This time, instead of building a single teleporter, he may install a network of teleport pads at selected road intersections across the farm. The farm road system is modeled as a connected, undirected, weighted graph.

There are N manure shipments. Shipment i must be moved from intersection s_i to intersection t_i. Each shipment is transported independently.

If Farmer John installs a set of teleport pads, then for any shipment he may choose either:

1. Drive directly from s_i to t_i, or
2. Use the teleport network once:
   • drive from s_i to any installed pad,
   • teleport instantly and for free to any other installed pad,
   • drive from that pad to t_i.

Teleportation between installed pads has zero cost and unlimited capacity.

However, each candidate pad location has a construction cost, and the total construction cost must not exceed the budget.

Your task is to choose which candidate pad locations to build in order to minimize the total driving distance over all shipments.

This is an optimization challenge: better solutions receive higher scores.

---

Input

The input describes one test file.

• The first line contains five integers
  V E M N C

  • V: number of intersections (1..V)
  • E: number of roads
  • M: number of candidate teleport-pad sites
  • N: number of shipments
  • C: total construction budget

• The next E lines each contain three integers
  u v w
  meaning there is an undirected road between intersections u and v with length w.

• The next M lines each contain two integers
  p_j cost_j
  meaning candidate site j is located at intersection p_j and costs cost_j to build.

• The next N lines each contain two integers
  s_i t_i
  describing a shipment from s_i to t_i.

All road lengths and construction costs are positive integers.

The graph is connected.

---

Output

Output a feasible set of candidate sites to build.

• The first line must contain a single integer K — the number of chosen sites.
• The next K lines must each contain one integer: the index of a chosen candidate site (an integer from 1 to M).

Feasibility requirements

Your output is feasible iff all of the following hold:

• 0 <= K <= M
• all chosen indices are distinct
• each chosen index is between 1 and M
• the sum of construction costs of the chosen sites is at most C

If your output is infeasible, your score for that test file is 0.

---

Objective

Let dist(a,b) be the shortest-path distance between intersections a and b in the road graph.

Let S be the set of chosen candidate sites, and let P(S) be their intersections.

For shipment i, define:

• Direct cost: direct_i = dist(s_i, t_i)

• Teleport-assisted cost:

  • if S is empty, this cost is treated as +infinity
  • otherwise
    tele_i = min_{x in P(S)} dist(s_i, x) + min_{y in P(S)} dist(t_i, y)

The shipment cost is

d_i = min(direct_i, tele_i)

The objective value of your output is

O = sum_{i=1..N} d_i

Your goal is to minimize O.

---

Scoring

For each test file, define the baseline solution as building no pads at all.

Its objective value is therefore

B = sum_{i=1..N} dist(s_i, t_i)

For a feasible submission with objective value O, the score for that test file is

score = round(1,000,000 * max(0, min(1, (B - O) / B )))

Since direct transport is always allowed, any feasible solution satisfies O <= B, so this is simply the relative improvement over the baseline, scaled to 1,000,000.

• Baseline solution: score 0
• Better solutions: higher scores
• Perfectly eliminating all driving distance: score 1,000,000

If your output is infeasible, the score is 0.

The total score of a submission is the sum of its scores over all test files.

---

Constraints

• 2 <= V <= 8000
• V-1 <= E <= 40000
• 1 <= M <= 3000
• 1 <= N <= 100000
• 1 <= C <= 10^12
• 1 <= w <= 10^9
• 1 <= cost_j <= 10^9
• 1 <= u, v, p_j, s_i, t_i <= V
• s_i != t_i
• candidate site intersections p_j are distinct

The exact optimum is intended to be computationally difficult in general; heuristic and approximation methods are expected.

• Time limit: 4 seconds
• Memory limit: 1024 MB

---

Example

Sample input

5 6 3 3 7
1 2 4
2 3 4
3 4 4
4 5 4
1 5 20
2 5 7
2 3
4 4
5 5
1 4
1 5
3 5

Sample output

2
1
2

Explanation

There are 3 candidate pad sites:

• site 1 at intersection 2, cost 3
• site 2 at intersection 4, cost 4
• site 3 at intersection 5, cost 5

The sample output builds sites 1 and 2, with total cost 3 + 4 = 7, which fits the budget.

Shortest direct shipment costs are:

• 1 -> 4: 12
• 1 -> 5: 11
• 3 -> 5: 8

So the baseline is B = 31.

With pads at intersections 2 and 4:

• 1 -> 4: drive 1 -> 2 (4), teleport 2 -> 4 (0), drive 4 -> 4 (0), total 4
• 1 -> 5: drive 1 -> 2 (4), teleport 2 -> 4 (0), drive 4 -> 5 (4), total 8
• 3 -> 5: best remains 8

Thus O = 4 + 8 + 8 = 20.

Relative improvement is (31 - 20) / 31 = 11/31, so the score for this file is approximately 354,839.