Bình luận

• 
  

  5

  

  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

• 
  

  0

  

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

  Cho em xin sol với ạ.