Thương vụ trên đồ thị DAG

Buổi 24 — Mock Contest Phase 1
Points
32
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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 -1 nế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$.
Draft saved