Vào năm 2992, phần lớn công việc đã do robot đảm nhận. Vì thế, nhiều người có rất nhiều thời gian rảnh, và gia đình bạn cũng vậy: họ vừa quyết định thực hiện một chuyến du hành giữa các hành tinh!

Có \(N\) hành tinh có thể đến, được đánh số từ \(0\) đến \(N-1\), cùng \(M\) tuyến tàu liên hành tinh. Tuyến tàu \(i\) (\(0 \le i < M\)) khởi hành từ hành tinh \(X[i]\) vào thời điểm \(A[i]\), đến hành tinh \(Y[i]\) vào thời điểm \(B[i]\) và có giá vé \(C[i]\).

Tàu là phương tiện duy nhất để di chuyển giữa các hành tinh. Vì vậy, bạn chỉ có thể xuống tàu tại hành tinh đích, và chuyến tàu tiếp theo phải khởi hành từ chính hành tinh đó; việc chuyển tuyến không tốn thời gian.

Một dãy tuyến tàu \(q[0],q[1],\ldots,q[P]\) là hợp lệ khi và chỉ khi, với mọi \(1 \le k \le P\):

và

Du hành giữa các hành tinh mất nhiều thời gian, và ngoài tiền vé tàu, chi phí ăn uống cũng rất đáng kể. May thay, các chuyến tàu liên hành tinh cung cấp thức ăn miễn phí không giới hạn. Cụ thể, nếu bạn đi tuyến tàu \(i\), tại bất kỳ thời điểm nào từ \(A[i]\) đến \(B[i]\), kể cả hai đầu mút, bạn có thể dùng miễn phí bao nhiêu bữa ăn tùy ý. Tuy nhiên, khi gia đình bạn ở trên một hành tinh \(i\) để chờ chuyến tàu tiếp theo, mỗi bữa ăn có giá \(T[i]\).

Gia đình bạn cần dùng \(W\) bữa ăn. Bữa ăn thứ \(i\) (\(0 \le i < W\)) có thể được dùng tức thời tại bất kỳ thời điểm nào trong đoạn từ \(L[i]\) đến \(R[i]\), kể cả hai đầu mút.

Tại thời điểm \(0\), gia đình bạn đang ở hành tinh \(0\). Hãy tính tổng chi phí nhỏ nhất để đến hành tinh \(N-1\). Nếu không thể đến đó, câu trả lời là \(-1\).

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

long long solve(int N, int M, int W, std::vector<int> T,
                std::vector<int> X, std::vector<int> Y,
                std::vector<int> A, std::vector<int> B, std::vector<int> C,
                std::vector<int> L, std::vector<int> R);

• \(N\): số hành tinh.
• \(M\): số tuyến tàu liên hành tinh.
• \(W\): số bữa ăn.
• \(T\): mảng có độ dài \(N\); \(T[i]\) là giá của mỗi bữa ăn trên hành tinh \(i\).
• \(X,Y,A,B,C\): năm mảng có độ dài \(M\); bộ \((X[i],Y[i],A[i],B[i],C[i])\) mô tả tuyến tàu thứ \(i\).
• \(L,R\): hai mảng có độ dài \(W\); cặp \((L[i],R[i])\) mô tả đoạn thời gian có thể dùng bữa ăn thứ \(i\).

Hàm phải trả về chi phí nhỏ nhất để đi từ hành tinh \(0\) đến hành tinh \(N-1\) nếu có thể đến được, và trả về \(-1\) nếu không thể.

Với mỗi trường hợp kiểm thử, hàm này được gọi đúng một lần.

Ví dụ

solve(3, 3, 1, {20, 30, 40}, {0, 1, 0}, {1, 2, 2},
      {1, 20, 18}, {15, 30, 40}, {10, 5, 40}, {16}, {19})

solve(3, 5, 6, {30, 38, 33}, {0, 1, 0, 0, 1}, {2, 0, 1, 2, 2},
      {12, 48, 26, 6, 49}, {16, 50, 28, 7, 54},
      {38, 6, 23, 94, 50}, {32, 14, 42, 37, 2, 4},
      {36, 14, 45, 40, 5, 5})

Hàm trả về `197`.

Ràng buộc

• \(2 \le N \le 10^5\).
• \(0 \le M,W \le 10^5\).
• \(0 \le X[i],Y[i] < N\) và \(X[i] \ne Y[i]\).
• \(1 \le A[i] < B[i] \le 10^9\).
• \(1 \le T[i],C[i] \le 10^9\).
• \(1 \le L[i] \le R[i] \le 10^9\).

Phân nhóm

1. 5 điểm: \(N,M,A[i],B[i],L[i],R[i] \le 10^3\) và \(W \le 10\).
2. 5 điểm: \(W=0\).
3. 30 điểm: Không có hai bữa ăn nào giao nhau về thời gian. Nói cách khác, với mọi thời điểm \(z\) thỏa mãn \(1 \le z \le 10^9\), có nhiều nhất một chỉ số \(i\) (\(0 \le i < W\)) sao cho:

1. 60 điểm: Không có ràng buộc bổ sung.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): \(N\ M\ W\).
• Dòng \(2\): \(T[0]\ T[1]\ \ldots\ T[N-1]\).
• Dòng \(3+i\) với \(0 \le i < M\): \(X[i]\ Y[i]\ A[i]\ B[i]\ C[i]\).
• Dòng \(3+M+i\) với \(0 \le i < W\): \(L[i]\ R[i]\).

Trình chấm mẫu in trên dòng đầu tiên giá trị do hàm solve trả về.

Nguồn

Olympic Tin học Châu Á - Thái Bình Dương 2024 (APIO 2024), bài Train. Đề và gói bài chính thức: APIO 2024 Tasks.