Weighted Paths Partition
Partition points into up to P disjoint paths. Edges later in a path cost more.
Given N=1000 points in 2D and constants P=100, q=1.15 (>1), partition all points into at most P disjoint paths (each path has at least 2 points, they cannot repeat). For a path \((v_0,\ldots,v_{k-1})\), let \(d_i\) be the distance of edge \((v_{i-1},v_{i})\). The path cost is \(C = \sum_{i=1}^{k-1} d_i \cdot q^{i}\), so later edges are multiplied by higher \(q^{i}\). The total cost is the sum over all paths: minimize it.
Instance: N = 1000 points, P = 100, q = 1.15. The file header line is "N P q", then N lines "id x y".
Solution format: First line: p, the number of paths. Then p lines: point ids for each path (space-separated, distinct, length ≥ 2). All points must appear exactly once.
Scoring: \(C_{\text{total}} = \sum_{\text{paths}} \sum_{i=1}^{k-1} d_i \cdot q^{i}\) Smaller is better. For a path \((v_0,\ldots,v_{k-1})\), cost = \(\sum_{i=1}^{k-1} d_i \cdot q^{i}\), with \(d_i\) the edge distances along the path.
Solution example: Download example