Minimize Population-Weighted Manhattan Travel Cost

Problem Statement

You are given a list of cities in a 2D grid, where each city i is defined by its coordinate (x_i, y_i) and a population w_i. Your task is to find a meeting point (X, Y) such that the total population-weighted Manhattan distance is minimized. The cost function is defined as:

Cost(X, Y) = Σ w_i * (|x_i - X| + |y_i - Y|)

Return the minimum cost and the meeting point (X, Y) as a list [cost, X, Y]. If multiple points yield the same minimum cost, choose the one with the smallest X, and then the smallest Y (lexicographical order).

Input

• cities: A list of lists where each element is [x_i, y_i, w_i].

Constraints

• 1 <= cities.length <= 10^5
• 0 <= x_i, y_i <= 10^6
• 1 <= w_i <= 1000

Examples

Example 1: Input: [[0, 0, 1], [2, 0, 1]] Output: [2, 1, 0] Explanation: The total weight is 2. Any point with X in [0, 2] and Y=0 yields a cost of 2. Among these, (0, 0) is the smallest coordinate.

Example 2: Input: [[0, 0, 10], [10, 10, 1]] Output: [10, 0, 0] Explanation: The weighted median for X is 0 (since 10 > 1), and similarly for Y.

def min_weighted_manhattan(cities: list[list[int]]) -> list[int]:
    # Implementation here