Có N thành phố 1…N nối bởi các con đường một chiều. Mỗi con đường có hai giá trị: độ dài và chi phí phải trả để đi qua. Bob ở thành phố 1. Bạn hãy giúp Bob tìm đường đi ngắn nhất đến thành phố N, biết rằng Bob chỉ có số tiền có hạn là K mà thôi.
Ai có hướng giải xin mời nêu ra để mọi người cùng tham khảo nha
Bạn có thể áp dụng thuật toán quay lui (có nhánh cận là tổng độ dài hiện tại luôn bé hơn K) để giải bài toán này.
toán rời rạc đây mà
bài toán tối ưu
phương pháp duyệt toàn cục hoặc nhánh cận ( có phần giống quay lui)
gần giống Bài Toán “đường đi ngắn nhất”
kinh điển
theo mình thì tim đương t/m số tiền k trước rồi so sánh chúng tìm đường ngắn nhất
Dpt quá lớn k trụ nổi với n lớn
Mình nghĩ là dijkstra kết hợp dk tổng cp < k là dc
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?