Tất cả thử thách
Trung bình 1 đã giải Tỷ lệ chấp nhận 100.0%

Shortest Weighted Routes

Find the minimum total route cost from city 1 to each city.

Bạn sẽ học được gì

  • Tìm đường đi ngắn nhất bằng thuật toán Dijkstra
  • Dùng hàng đợi ưu tiên để chọn thành phố tiếp theo
  • Bỏ qua các phần tử đã cũ trong hàng đợi

Đề 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ụ

Ví dụ 1
Đầ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.

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 ННикита Python 695 ms - 5/5 Xem code

Học hỏi từ người khác

Giải pháp cộng đồng

Cảnh báo: Có 1 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.