# VNOI - Coding Challenge #3 - Đổ Xăng

## Đề bài
Cho một đồ thị vô hướng liên thông gồm $n$ đỉnh và $m$ cạnh có dạng $(x, y, w)$ nối đỉnh $x$ và đỉnh $y$ và có trọng số $w$, muốn đi qua cạnh này ta cần tiêu thụ $w$ lít xăng.

Cho trước hai đỉnh $st$ và $en$, ta cần tìm cách di chuyển từ đỉnh $st$ đến đỉnh $en$ thông qua $m$ cạnh trên đồ thị, lít xăng tối đa ta có thể có ở một thời điểm là $t$, ban đầu ở đỉnh $st$ ta không có lít xăng nào.

Có $s$ đỉnh có trạm xăng, trạm xăng thứ $i$ được phân bố ở đỉnh $p_i$ và có chi phí cho một lít xăng là $c_i$. Ở mỗi trạm xăng có thể mua tùy ý lượng xăng miễn sao lượng xăng hiện có không vượt qua sức chứa $t$.

Yêu cầu: Tìm số tiền ít nhất cần bỏ ra để đi từ đỉnh $st$ đến đỉnh $en$.

## Subtask 1, 2: $t \leq 500$
Gọi $d(u, t)$ là số tiền nhỏ nhất để đi từ đỉnh $st$ đến đỉnh $u$ và còn lại $t$ lít xăng khi đến đỉnh $u$.

Xét một trạng thái $d(u, t)$ và một cạnh $(u, v, w)$, ta chuyển trạng thái như sau:

- Khi có trạm xăng tại $u$: $d(u, t + 1) \leftarrow d(u, t) + c_u$
- Khi $t \geq w$: $d(v, t - w) \leftarrow d(u, t)$

Để tính $d$, ta sử dụng thuật toán **Dijkstra**.

Độ phức tạp: $O(n \times t \times \log_{2}(n))$

## Subtask 3:
Giả sử các trạm xăng mà ta lần lượt đi qua và có mua ít nhất một lít xăng trên một đường đi tối ưu là $k_1, k_2, \ldots k_l$. Ta nhận thấy chi phí của trạm tiếp theo luôn nhỏ hơn hoặc bằng chi phí của trạm trước, tức $c_{k_i} \geq c_{k_{i + 1}}$ với mọi $i \in [1, l - 1]$.

Từ đây ta sẽ sắp xếp thứ tự các trạm theo chi phí mua giảm dần, gọi $cost_i$ là chi phí mua một lít xăng ở trạm thứ $i$ trong tổng cộng $s$ trạm. Ta gọi $d(i, j)$ là số lít xăng ít nhất cần sử dụng để đi từ trạm thứ $i$ đến trạm thứ $j$ theo thứ tự sắp xếp, ta tính $d$ bằng cách sử dụng thuật toán **Dijkstra**.

Sau đó sử dụng thuật toán quy hoạch động để tính chi phí nhỏ nhất. Xét thứ tự các trạm đã được sắp xếp, ta gọi $dp(i, j)$ là số tiền nhỏ nhất để đi từ đỉnh $st$ đến trạm thứ $i$ theo thứ tự các trạm và còn lại $j$ lít xăng, ta chuyển trạng thái như sau:

- Mua xăng tại trạm thứ $i$: $dp(i, j) \leftarrow dp(i, j - 1) + cost_i$
- Di chuyển giữa các trạm: $dp(i, j) \leftarrow dp(l, j + d(l, i))$ với $l < i; j + d(l, i) \leq t$

Sau khi tính $dp$, ta xét các trạng thái $dp(i, j)$, nếu lượng xăng ít nhất cần dùng để đi từ trạm thứ $i$ đến đỉnh $en$ không vượt quá $j$, ta sẽ xét chúng làm số tiền nhỏ nhất cần bỏ ra.

Độ phức tạp: $O(s \times n + s^2 \times t)$