Xe điện vượt đường dài
Points
34
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Mạng lưới đường bộ gồm $N$ thành phố đánh số từ $1$ đến $N$ và $M$ tuyến đường hai chiều. Tuyến đường thứ $i$ nối $u_i, v_i$ và tiêu tốn $d_i$ đơn vị pin để đi qua.
Bạn lái một chiếc xe điện có dung lượng pin tối đa là $C$ đơn vị. Ban đầu xe đang ở thành phố $1$ với lượng pin bằng $0$. Tại thành phố $i$, bạn có thể sạc thêm $1$ đơn vị pin với chi phí $P_i$ (có thể sạc nhiều lần, nhưng lượng pin không được vượt quá $C$).
Hãy tìm tổng chi phí sạc pin nhỏ nhất để đi từ thành phố $1$ đến thành phố $N$, hoặc in ra -1 nếu không thể đến được $N$.
Dữ liệu vào
- Dòng đầu chứa ba số nguyên $N, M, C$ ($1 \le N \le 500$, $0 \le M \le 2000$, $1 \le C \le 100$).
- Dòng thứ hai chứa $N$ số nguyên $P_1, P_2, \dots, P_N$ ($1 \le P_i \le 10^9$).
- $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u_i, v_i, d_i$ ($1 \le u_i, v_i \le N$, $1 \le d_i \le 100$).
Dữ liệu ra
- Một số nguyên duy nhất là chi phí nhỏ nhất, hoặc
-1nếu không thể đến $N$.
Ví dụ
| Input | Output |
|---|---|
| 4 4 10 5 2 10 1 1 2 4 2 4 8 1 3 3 3 4 5 |
36 |
| 3 2 5 10 2 1 1 2 6 2 3 4 |
-1 |
Giới hạn
- $1 \le N \le 500$, $0 \le M \le 2000$, $1 \le C \le 100$.
- $1 \le P_i \le 10^9$, $1 \le d_i \le 100$.
Community Discussion