Thương vụ trên đồ thị DAG
Points
32
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho một đồ thị có hướng không chu trình (DAG) gồm $N$ đỉnh đánh số từ $1$ đến $N$ và $M$ cung. Mỗi cung $u \to v$ có chi phí đi qua là $c$ và mang lại phần thưởng là $r$.
Bạn xuất phát tại đỉnh $1$ với ngân sách tối đa $B$ và muốn đi tới đỉnh $N$. Tổng chi phí các cung trên đường đi không được vượt quá $B$.
Hãy tìm tổng phần thưởng lớn nhất có thể thu được khi đi từ $1$ đến $N$, hoặc in ra -1 nếu không có đường đi hợp lệ.
Dữ liệu vào
- Dòng đầu chứa ba số nguyên $N, M, B$ ($1 \le N \le 500$, $0 \le M \le 2000$, $0 \le B \le 500$).
- $M$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $u, v, c, r$ ($1 \le u, v \le N$, $0 \le c \le 500$, $1 \le r \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là tổng phần thưởng lớn nhất, hoặc
-1nếu không thể đến $N$.
Ví dụ
| Input | Output |
|---|---|
| 4 5 10 1 2 4 10 2 4 5 20 1 3 2 5 3 4 6 12 2 3 1 3 |
30 |
| 3 2 5 1 2 4 10 2 3 4 20 |
-1 |
Giới hạn
- $1 \le N \le 500$, $0 \le M \le 2000$, $0 \le B \le 500$.
- $0 \le c \le 500$, $1 \le r \le 10^9$.
Community Discussion