Hành trình đổ xăng tiết kiệm
Points
58
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Một chiếc xe xuất phát từ thành phố $1$ với bình xăng rỗng và muốn đến thành phố $N$. Dung tích tối đa của bình xăng là $C$. Tại thành phố $i$, giá mua $1$ lít xăng là $P_i$ (chỉ được mua từng lít nguyên). Có $M$ con đường hai chiều, con đường nối $u$ và $v$ tiêu tốn $w$ lít xăng. Hãy tìm tổng chi phí mua xăng ít nhất để đến được thành phố $N$, hoặc -1 nếu không thể đến nơi.
Dữ liệu vào
- Dòng đầu chứa ba số nguyên $N, M, C$ ($1 \le N \le 100$, $0 \le M \le 1000$, $1 \le C \le 50$).
- Dòng thứ hai chứa $N$ số nguyên $P_1, P_2, \dots, P_N$ ($1 \le P_i \le 10^6$).
- $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ ($1 \le u, v \le N$, $1 \le w \le 100$).
Dữ liệu ra
- Một số nguyên duy nhất là chi phí nhỏ nhất, hoặc
-1.
Ví dụ
| Input | Output |
|---|---|
| 4 4 5 10 2 5 8 1 2 3 2 3 4 3 4 2 1 4 6 |
45 |
| 3 2 3 5 10 2 1 2 4 2 3 2 |
-1 |
Giới hạn
- $1 \le N \le 100$, $0 \le M \le 1000$, $1 \le C \le 50$
- $1 \le P_i \le 10^6$, $1 \le w \le 100$
Community Discussion