Subtask 1: ~p_i = 1 \, \forall \, 1 \leq i \leq m~

Vì mọi chuyến bay đều thuộc hãng Pekoland Airlines (nghĩa là không có chuyến bay nào bị hủy), ta có thể giải subtask này bằng thuật toán Dijkstra. Gọi ~dist(u)~ là thời gian sớm nhất Aqua có thể đến thành phố ~u~. Ở mỗi bước trong thuật toán Dijkstra, khi xét thành phố ~u~, ta duyệt qua các chuyến bay ~[u, v, x, y, *]~ thỏa mãn ~x \geq dist(u)~, sau đó cập nhật ~dist(v) = \min(dist(v),\,y)~. Độ phức tạp của thuật toán là ~O((n+m)\log(n+m))~.

Subtask 2: ~\sum n \le 1\,000~, ~\sum m \le 1\,000~

Ta có thể giải subtask này bằng quy hoạch động. Gọi ~dp(u, t, i)~ là thời gian sớm nhất Aqua có thể đến thành phố ~n~ từ thành phố ~u~, biết thời điểm hiện tại là ~t~ và PekoJet Air có thể hủy tối đa ~i~ chuyến bay. Từ trạng thái ~(u, t, i)~, Aqua có thể thực hiện một trong hai hành động sau:

• Không làm thủ tục chuyến bay nào: chuyển sang trạng thái ~(u, t+1, i)~
• Chọn một trong các chuyến bay có dạng ~[u, v, t, y, p]~ để làm thủ tục. Có hai trường hợp xảy ra:
  • Chuyến bay không bị hủy: chuyển sang trạng thái ~(v, y, i)~
  • Chuyến bay bị hủy (có thể xảy ra khi ~p = 2~): chuyển sang trạng thái ~(u, t+1, i-1)~

Vậy ~dp(u, t, i)~ là giá trị nhỏ nhất trong số:

• ~dp(u, t+1, i)~
• ~dp(v, y, i)~ với mọi chuyến bay có dạng ~[u, v, t, y, 1]~
• ~\max(dp(v, y, i),\, dp(u, t+1, i-1))~ với mọi chuyến bay có dạng ~[u, v, t, y, 2]~

Tất nhiên giới hạn của ~t~ là rất lớn, do đó công thức trên không khả thi. Để giảm độ phức tạp, để ý có tối đa ~2m~ cặp ~(u, t)~ sao cho ở thời điểm ~t~ có ít nhất một chuyến bay cất/hạ cánh tại ~u~. Vậy với mỗi thành phố ~u~, ta chỉ cần lưu lại những mốc thời gian có chuyến bay cất/hạ cánh. Độ phức tạp của thuật toán trên do đó được giảm xuống ~O(mk)~

Subtask 3: Không có ràng buộc gì thêm

Trước hết, ta xét phiên bản đơn giản hơn của bài toán gốc: chỉ cần kiểm tra Aqua có đến được thành phố ~n~ hay không. Theo đó, công thức quy hoạch động để giải subtask 2 sẽ trả về ~0~ hoặc ~1~ (với ý nghĩa có đến được ~n~ từ trạng thái ~(u, t, i)~ hay không). Mặt khác, nhận xét nếu ~dp(u, t, i) = 1~ thì ~dp(u, t, j) = 1~ với mọi ~j \leq i~; ngược lại, nếu ~dp(u, t, i) = 0~ thì ~dp(u, t, j) = 0~ với mọi ~j \geq i~. Ta có thể áp dụng kĩ thuật đổi biến: thay vì tính ~dp(u, t, i)~, ta sẽ tính ~opt(u, t)~ trả về ~i~ lớn nhất sao cho ~dp(u, t, i) = 1~. Ta kết luận có thể đến được ~n~ từ ~1~ khi và chỉ khi ~opt(1, 0) \geq k~. Tương tự subtask 2, ~opt(u, t)~ là giá trị lớn nhất trong số:

• ~opt(u, t+1)~
• ~opt(v, y)~ với mọi chuyến bay có dạng ~[u, v, t, y, 1]~
• ~\min(opt(v, y),\, opt(u, t+1) + 1)~ với mọi chuyến bay có dạng ~[u, v, t, y, 2]~

Vậy độ phức tạp để tính mọi ~opt(u, t)~ là ~O(m)~.

Quay trở lại với bài toán gốc, ta cần tìm thời điểm ~x~ nhỏ nhất sao cho Aqua có thể đến ~n~ không muộn hơn ~x~. Ta tìm kiếm nhị phân kết quả, với mỗi giá trị ~x~ ta chỉ xét những chuyến bay hạ cánh không muộn hơn ~x~ và tính ~opt~ như trên. Độ phức tạp để giải bài toán gốc là ~O(m \log A)~ với ~A = 10^9~ là khoảng giá trị của ~x~, hoặc ~O(m \log m)~ nếu chỉ xét ~x~ trong số các thời điểm hạ cánh của ~m~ chuyến bay.

ahjhj d0 ng0k