Elearning CodePath – CTP Online Judge

Hành trình tiếp nhiên liệu

DJK06

## Đề bài

Có `n` thành phố và `m` con đường hai chiều. Xe của bạn có bình nhiên liệu chứa tối đa `C` đơn vị.

Ở thành phố `i`, giá mua 1 đơn vị nhiên liệu là `p[i]`. Ban đầu xe ở thành phố `s` với `0` đơn vị nhiên liệu. Bạn muốn đi đến thành phố `t`.

Mỗi con đường nối `u` và `v` cần đúng `fuel` đơn vị nhiên liệu để đi qua. Khi đi qua đường đó, lượng nhiên liệu trong bình giảm đi `fuel`.

Tại mỗi thành phố, bạn có thể mua thêm từng đơn vị nhiên liệu, miễn là tổng nhiên liệu trong bình không vượt quá `C`.

Hãy tìm số tiền ít nhất cần trả để đi từ `s` đến `t`.

Nếu không thể đi đến `t`, in ra `-1`.

## Dữ liệu vào

- Dòng đầu chứa năm số nguyên `n`, `m`, `C`, `s`, `t`.
- Dòng thứ hai chứa `n` số nguyên `p[1], p[2], ..., p[n]`.
- `m` dòng tiếp theo, mỗi dòng chứa ba số nguyên `u`, `v`, `fuel`, mô tả đường hai chiều giữa `u` và `v`.

## Dữ liệu ra

In ra số tiền ít nhất cần trả, hoặc `-1` nếu không thể đi tới đích.

## Ràng buộc

- `2 <= n <= 500`
- `0 <= m <= 3000`
- `1 <= C <= 1000`
- `1 <= s, t <= n`
- `s != t`
- `1 <= p[i] <= 10^6`
- `1 <= fuel <= 2000`

## Subtask

- Subtask 1: `n <= 8`, `C <= 10`.
- Subtask 2: `n <= 100`, `C <= 100`.
- Subtask 3: Không có ràng buộc bổ sung.

## Ví dụ

```text
4 4 5 1 4
5 2 10 1
1 2 3
2 4 3
1 3 5
3 4 1
```

```text
21
```

## Giải thích ví dụ

Một cách tối ưu:

- Ở thành phố `1`, mua `3` đơn vị nhiên liệu, tốn `3 * 5 = 15`.
- Đi từ `1` đến `2`, hết `3` đơn vị.
- Ở thành phố `2`, mua `3` đơn vị nhiên liệu, tốn `3 * 2 = 6`.
- Đi từ `2` đến `4`.

Tổng chi phí là `15 + 6 = 21`.

✅ Đã AC: 0 / 0 submissions