thảo luận [Học Tập] Topic thuật toán

  • Người tạo chủ đề Người tạo chủ đề unknowpc90
  • Ngày bắt đầu Ngày bắt đầu
reachable đầu tiên chưa chắc là ngắn nhất bác, đỉnh nào phải là được chọn để đi tiếp mới là ngắn nhất chứ ạ
Đúng rồi. Do cách hiểu của t là reachable có nghĩa là khi cái đỉnh đó được lấy từ trong heap ra.
Nhưng mà phải nói như thím mới đúng.

Không được đâu, vì theo đề bài thì đồ thị là có hướng, đường đi ở hai chiều không nhất thiết tương đương.

--
Edited: Nếu dùng với đồ thị ngược của input thì có khi được.

Vậy thuật toán sẽ là như này:

  • B1: đặt E' = <đảo chiều các cạnh của E>
  • B2: Chạy Dijkstra (V, E') với bắt đầu là t. Dừng khi tìm được đường đi ngắn nhất đến tất cả N điểm nguồn,
  • B3: Output 3 đường đi ngắn nhất trong số N

T nói là đi ngược lại mà, :big_smile: .
Mà không cần phải tìm ra tất cả N điểm đâu. Chỉ cần đảm bảo số điểm có shortest path đã tìm được + số điểm add thêm vào heap = 3 như đề bài là được. Vì yêu cầu chỉ cần tìm 3 thôi. :big_smile:
 
T nói là đi ngược lại mà, :big_smile: .
Mà không cần phải tìm ra tất cả N điểm đâu. Chỉ cần đảm bảo số điểm có shortest path đã tìm được + số điểm add thêm vào heap = 3 như đề bài là được. Vì yêu cầu chỉ cần tìm 3 thôi. :big_smile:


tức là vẫn phải tìm từ t đến N đỉnh kia xong chọn 3 thằng min đúng k ạ, quan trọng phải đảo chiều đồ thị ban đầu

Đúng là tìm đến 3 là được, vì Dijkstra thì điểm nào được pop ra từ heap sớm hơn sẽ gần hơn các điểm pop ra sau.

Sent from Xiaomi M2007J20CG using vozFApp
 
Các bác cho em xin ý tưởng bài này với. Em mới nghĩ ra mỗi duyệt trâu và dùng deque để tối ưu
 

Tệp đính kèm

  • 1668698774240.png
    1668698774240.png
    45,1 KB · Lượt xem: 94
em thấy để tìm ceil(a/b) với a và b là int thì người ta dùng công thức (a + b - 1)/b. Có bác nào giải thích giúp em sao lại có công thức như vậy được không ạ?
 

Thống kê chủ đề

Ngày tạo
unknowpc90,
Người trả lời cuối
Spaghetti Code,
Trả lời
1.460
Lượt xem
154.038
Quay lại
Lên đầu trang