Tối Ưu Thời Gian Và Chi Phí

Buổi 19 — Đường đi ngắn nhất
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho đồ thị có hướng gồm $N$ đỉnh và $M$ cung. Mỗi cung $(u, v)$ có hai thông số: chi phí $c$ ($c \ge 0$) và thời gian di chuyển $t$ ($t \ge 0$). Bạn có ngân sách tối đa $B$. Hãy tìm tổng thời gian ngắn nhất để đi từ đỉnh $1$ đến đỉnh $N$ sao cho tổng chi phí không vượt quá $B$. Nếu không có đường đi thỏa mãn, in ra -1.

Dữ liệu vào
  • Dòng đầu chứa ba số nguyên $N, M, B$ ($1 \le N \le 200$, $0 \le M \le 1000$, $0 \le B \le 1000$).
  • $M$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $u, v, c, t$ ($1 \le u, v \le N$, $0 \le c \le 1000$, $0 \le t \le 10^9$).
Dữ liệu ra
  • In ra tổng thời gian ngắn nhất có thể với tổng chi phí $\le B$, hoặc -1 nếu không tồn tại.
Ví dụ
Input Output
4 4 5\n1 2 2 5\n2 4 2 5\n1 3 4 1\n3 4 2 1 10
4 4 6\n1 2 2 5\n2 4 2 5\n1 3 4 1\n3 4 2 1 2
Giới hạn
  • $1 \le N \le 200$
  • $0 \le M \le 1000$
  • $0 \le B \le 1000$
  • $0 \le c \le 1000$, $0 \le t \le 10^9$
Draft saved