Ola Inter-City Network Optimization
Ola is rapidly expanding its autonomous vehicle network across various cities. To ensure seamless operations and robust service delivery, it's crucial to establish reliable connectivity within distinct geographical regions. This problem challenges you to design an efficient algorithm that optimizes road construction costs to achieve the necessary connectivity for each defined region.
Implement a function calculateRegionConnectivityCosts that determines the minimum total cost of building roads to connect all cities within each specified region.
i-th element represents the minimum connectivity cost for region i.N: An integer, representing the total number of cities (0 to N-1).
regionIds: An array of integers regionIds[i] where regionIds[i] specifies the region ID (0 to K-1) to which city i belongs. Each city belongs to exactly one region.
roads: A 2D array of integers [[u, v, cost], ...] representing potential roads. u and v are city indices (0 to N-1), and cost is the non-negative integer cost to build a road between them. Roads are undirected.
Returns: An array of long integers of size K (where K is the number of distinct regions, determined by the maximum region ID in regionIds + 1). result[i] should be the minimum cost to connect all cities in region i. If a region contains only one city, its connectivity cost is 0.
Examples
Example 1
Input:
N = 4, regionIds = [0, 0, 1, 1], roads = [[0, 1, 10], [1, 2, 5], [2, 3, 8]]
Output:
[10, 8]
Note:
Region 0 has cities {0, 1}. The road (0,1) with cost 10 connects them. Region 1 has cities {2, 3}. The road (2,3) with cost 8 connects them. The road (1,2) connects cities from different regions and is not needed for intra-region connectivity.
Example 2
Input:
N = 5, regionIds = [0, 0, 0, 1, 1], roads = [[0, 1, 10], [1, 2, 5], [0, 2, 12], [3, 4, 7], [1, 3, 20]]
Output:
[15, 7]
Note:
Region 0 has cities {0, 1, 2}. To connect them, we consider roads (1,2,5) and (0,1,10). Total cost: 5 + 10 = 15. The road (0,2,12) is redundant as (0,1,2) already forms a path 0-1-2 with lower total cost. Region 1 has cities {3, 4}. Road (3,4,7) connects them for a cost of 7. Road (1,3,20) connects cities from different regions.
Example 3
Input:
N = 6, regionIds = [0, 1, 0, 1, 2, 2], roads = [[0,2,10], [1,3,5], [0,1,1], [2,3,2], [4,5,15]]
Output:
[5, 5, 15]
Note:
Cities by region: R0={0,2}, R1={1,3}, R2={4,5}. Sorted roads by cost: (0,1,1), (2,3,2), (1,3,5), (0,2,10), (4,5,15).
Constraints
1 <= N <= 10^51 <= K <= N (where K is the number of distinct regions)0 <= regionIds[i] < K for all i0 <= M <= 2 * 10^5 (number of potential roads)0 <= u, v < N, u != v for any road [u, v, cost]0 <= cost <= 10^9 for any roadN over all test cases will not exceed 5 * 10^5.M over all test cases will not exceed 5 * 10^5.2^31 - 1, so use 64-bit integers (long in Java/C++, number in JS/TS) for total costs.Loading editor...