Hành trình đổ xăng tiết kiệm

General
Points
58
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved