Olympic Sinh Viên 2022 - Chuyên tin - Nâng cấp tuyến đường

Xem dạng PDF
Gửi bài giải
Điểm: 0,10 (OI)
Giới hạn thời gian: 4.0s
Giới hạn bộ nhớ: 1G
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    nmk05022006  đã bình luận lúc 4, Tháng 12, 2025, 15:20

    Code AC


  • 0
    quochungpro2019  đã bình luận lúc 18, Tháng 10, 2025, 2:05

    test case 1 bị sai phải là 14 16 16 chứ nhỉ


    • 0
      drikbest10  đã bình luận lúc 21, Tháng 11, 2025, 12:17

      đổi cạnh 1 3 thanh 11 ta thu được đường đi ngắn nhất là 15


  • 3
    YougiTuber  đã bình luận lúc 20, Tháng 9, 2025, 13:59

    Spoil⚠️

    Giả sử nếu không thay cạnh nào, thì kết quả chính là đường đi ngắn nhất từ đỉnh ~1~ đến ~s~, ta có thể tính bằng Dijkstra trước

    Trong trường hợp có thay thế một cạnh từ ~w~ thành ~t_0~, thì giá trị đường đi sẽ giảm ~w~ và tăng ~t_0~.

    Để kết quả tốt nhất, cần tham lam bằng cách xóa cạnh lớn nhất đi.

    Ta sẽ tính một mảng Dijkstra lưu giá trị đường đi ngắn nhất từ ~1~ đến ~s~ với trạng thái là đã xóa một cạnh trên đường đi từ ~1~ đến ~s~ hay chưa (hay coi trọng số ~w = 0~, khi tính mảng đường đi ngắn nhất này, thì cạnh bị xóa đi sẽ tự động là cạnh lớn nhất trên đường đi đó.

    Kết quả cuối cùng của bài toán là min(~d[0][s], d[1][s] + t_0~)