Free Contest Testing Round 37 - ROADRAIL2

Xem dạng PDF

Gửi bài giải

Điểm: 0,70 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M

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

Lưu ý: các bạn không nhập, xuất dữ liệu bằng file kể cả khi đề bài có yêu cầu. Đọc, ghi dữ liệu được thực hiện ở stdin và stdout.


Bình luận

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



  • 2
    YougiTuber  đã bình luận lúc 28, Tháng 4, 2025, 22:02 sửa 2

    Spoil thuật⚠️

    Dễ dàng nhìn ra cách làm dijkstra

    Công thức

    ~d[x][u][cnt]~ là đường đi ngắn nhất từ ~0~ đến ~u~, cạnh cuối cùng sử dụng là ~x~ (~x~ là ~0~ hoặc ~1~), đã dùng ~cnt~ lần chuyển trạng thái cạnh

    Số lần chuyển trạng thái cạnh tối đa là ~n~ lần

    Chuyển trạng thái của mảng ~d~

    Đi từ đỉnh ~u~ qua đỉnh ~v~ trong số cạnh là ~w~, loại cạnh là ~nx~, từ trạng thái

    ~d[x][u][cnt] + w \rightarrow d[nx][v][cnt + (x \ne nx)]~

    Tuy nhiên số trạng thái quá nhiều, sẽ dẫn đến TLE khi Dijkstra

    Vì vậy để tối ưu, ta làm như sau:

    Nếu ~d[x][u][cnt] < d[x][u][cnt+1]~, tức là đến ~u~ bằng nhiều lần chuyển trạng thái cạnh, lại tốn chi phí nhiều hơn, thì khi cộng thêm chi phí ~c~ của việc chuyển trạng thái cạnh, mọi trạng thái lớn hơn ~cnt~ đều không tối ưu bằng trạng thái ~cnt~, nên ta có thể continue sớm giúp giảm độ phức tạp

    Gọi mảng ~best[x][u]~ là số lần chuyển trạng thái ít nhất cần sử dụng, khi muốn đến ~u~ và cạnh cuối cùng có trạng thái là ~x~, nếu ~cnt > best[x][u]~ Ta sẽ continue tại nó. Ngược lại gán ~best[x][u] = cnt~.

    Kết quả cho mỗi trường hợp, ta sẽ thử mọi trạng thái ~cnt~ và ~x~ có thể.

    Độ phức tạp

    ~O((m + 2 \times n^2) \times log(m) + q \times n)~

    Free Contest Testing Round 13 - ROADRAIL2


  • 1
    ITK11_ThanhDanh  đã bình luận lúc 5, Tháng 6, 2024, 10:33

    Cho em xin sol với ạ.