Xe điện vượt đường dài

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