Problem
Find the minimum total route cost from city 1 to each city. Routes are directed: [u, v, cost] allows travel from u to v, not automatically back. You may use several routes. City 1 costs 0 to reach. Every city is reachable from city 1.
Implement shortest_weighted_routes(cities, routes).
Input
cities: Number of cities, numbered from 1.
routes: Directed routes [from_city, to_city, cost].
Output
Return the minimum costs in city order, starting with city 1.
Constraints
1 ≤ cities ≤ 100,000. 0…200,000 routes; endpoints are 1…cities. Costs are integers from 1 to 1,000,000,000. Parallel routes and self-loops are allowed. Distances fit signed 64-bit.
Examples
Input:
cities = 3
routes = [
[1, 2, 5],
[1, 3, 1],
[3, 2, 2]
]
Expected output:
expected = [0, 3, 1]Input:
long long cities = 3;
std::vector<std::vector<long long>> routes = {
{1, 2, 5},
{1, 3, 1},
{3, 2, 2}
};
Expected output:
std::vector<long long> expected = {0, 3, 1};Input:
long cities = 3;
long[][] routes = new long[][] {
new long[] {1, 2, 5},
new long[] {1, 3, 1},
new long[] {3, 2, 2}
};
Expected output:
long[] expected = new long[] {0, 3, 1};Explanation
City 3 costs 1. Going from 1 through 3 to 2 costs 1 + 2 = 3, cheaper than the direct cost of 5.
Input:
cities = 1
routes = []
Expected output:
expected = [0]Input:
long long cities = 1;
std::vector<std::vector<long long>> routes = {};
Expected output:
std::vector<long long> expected = {0};Input:
long cities = 1;
long[][] routes = new long[][] {};
Expected output:
long[] expected = new long[] {0};Explanation
The only city is the starting city. No travel is needed, so its distance is 0.
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
All route costs are positive, so always expand the currently cheapest unreached city next.
Hint 2
Build directed adjacency lists and use a priority queue to repeatedly relax outgoing routes.
Hint 3
Parallel routes and self-loops are fine; only update when a newly found path is cheaper.
Expected complexity
O((cities + routes) log cities) time, O(cities + routes) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.