Đề bài
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.
Ràng buộc
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.
Ví dụ
Đầu vào:
cities = 3
routes = [
[1, 2, 5],
[1, 3, 1],
[3, 2, 2]
]
Kết quả mong đợi:
expected = [0, 3, 1]Đầu vào:
long long cities = 3;
std::vector<std::vector<long long>> routes = {
{1, 2, 5},
{1, 3, 1},
{3, 2, 2}
};
Kết quả mong đợi:
std::vector<long long> expected = {0, 3, 1};Đầu vào:
long cities = 3;
long[][] routes = new long[][] {
new long[] {1, 2, 5},
new long[] {1, 3, 1},
new long[] {3, 2, 2}
};
Kết quả mong đợi:
long[] expected = new long[] {0, 3, 1};Giải thích
City 3 costs 1. Going from 1 through 3 to 2 costs 1 + 2 = 3, cheaper than the direct cost of 5.
Đầu vào:
cities = 1
routes = []
Kết quả mong đợi:
expected = [0]Đầu vào:
long long cities = 1;
std::vector<std::vector<long long>> routes = {};
Kết quả mong đợi:
std::vector<long long> expected = {0};Đầu vào:
long cities = 1;
long[][] routes = new long[][] {};
Kết quả mong đợi:
long[] expected = new long[] {0};Giải thích
The only city is the starting city. No travel is needed, so its distance is 0.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Mọi chi phí đường đi đều dương, nên luôn mở rộng thành phố chưa thăm có chi phí nhỏ nhất trước.
Gợi ý 2
Xây dựng danh sách kề có hướng và dùng priority queue để liên tục relax các route đi ra.
Gợi ý 3
Parallel routes và self-loops đều được; chỉ cập nhật khi đường mới tìm được rẻ hơn.
Độ phức tạp mong đợi
thời gian O((cities + routes) log cities), bộ nhớ phụ O(cities + routes)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.