Chi phí phát sinh (chiphips.*)

Đất nước Anpha có \(n\) thành phố được đánh số \(1,2,3,\ \ldots,n\). Giữa các thành phố này có \(m\) tuyến đường hai chiều đảm bảo kết nối giữa \(n\) thành phố. Mỗi tuyến đường thứ \((1 \leq i \leq n)\)được mô tả bởi cặp số \(\left( u_{i},v_{i} \right)\) kết nối trực tiếp hai thành phố \(u_{i}\) và \(v_{i}\) \(\left( u_{i} ≠ v_{i} \right)\) và được gán hai số nguyên dương \(c_{i}\), \(d_{i}\), trong đó \(c_{i}\) là độ đẹp và \(d_{i}\)là chi phí phát sinh khi đi qua tuyến đường.

Giả sử \(s\) và \(t\) là hai thành phố của đất nước Anpha. Một công ty ABC đang cần vận chuyển một chuyến hàng có trọng lượng 𝑊 từ thành phố 𝑠 tới thành phố 𝑡. Ta gọi một đường đi từ \(s\) đến \(t\) là một dãy \(z_{0},z_{1},z_{2},....,z_{k - 1},z_{k}\), trong đó \(z_{0} = s,\ z_{k} = t,\ \left( z_{i - 1},\ z_{i} \right)\)là tuyến đường với \(i = 1,2,...,k\). Chi phí cần vận chuyển một chuyến hàng có trọng lượng 𝑊 từ thành phố \(s\) đến thành phố \(t\) theo đường đi nói trên là:

\[d\left( z_{0},z_{1} \right) + d\left( z_{1},z_{2} \right) + ... + d\left( z_{k - 1},z_{k} \right) + \frac{W}{C_{\min}}\]

Trong đó \(d\left( z_{i - 1},\ z_{i} \right)\)là chi phí phát sinh của tuyến đường \(\left( z_{i - 1},\ z_{i} \right)\), \(C_{\min}\) là độ đẹp nhỏ nhất trong các tuyến đường trên đường đi mà xe hàng đi qua.

Yêu cầu: Cho trước hai thành phố s và t. Hãy tìm đường đi để vận chuyển một chuyến hàng có trọng lượng \(W\)với chi phí nhỏ nhất.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên \(n,\ m\ (2 \leq n \leq 150,\text{ 1} \leq m \leq 5000)\), mỗi số cách nhau một khoảng trắng;

• Dòng thứ hai chứa ba số nguyên dương \(s,\ t,\ W\ (1 \leq s,t \leq n;\ 1 \leq W \leq 10^{4})\), mỗi số cách nhau một khoảng trắng;

• Dòng thứ \(i\) trong số \(m\) dòng tiếp theo chứa bốn số nguyên dương \(u_{i},v_{i},c_{i},d_{i}\ \)mô tả thông tin về con đường thứ \(i\ \left( 1 \leq u_{i},\ v_{i} \leq n;\text{ 1} \leq c_{i},\ d_{i} \leq 10000,\ i = \ 1,2,\ .\ .\ .\ ,\ m \right)\), mỗi số cách nhau một khoảng trắng.

Kết quả: Ghi một số duy nhất là chi phí nhỏ nhất để vận chuyển chuyến hàng (kết quả làm tròn đến hai chữ số sau dấu thập phân).

Ví dụ:

Input	Output	hình minh họa
4 5 1 3 8 1 2 1 1 1 3 1 4 1 4 2 3 3 4 5 2 3 2 1 2	9.00

Ràng buộc:

+ Subtask1. Có 40% số test ứng với 40% số điểm của bài thỏa mãn \(\mathbf{c}_{\mathbf{i}}\mathbf{=}\mathbf{d}_{\mathbf{i}}\mathbf{= 1\ (\forall i = 1,2,3,...,m)}\);

+ Subtask2. Có 30% số test ứng với 30% số điểm của bài thỏa mãn \(\mathbf{c}_{\mathbf{i}}\mathbf{= 1\ (\forall i = 1,2,3,...,m)}\);

+ Subtask3. Có 20% số test ứng với 20% số điểm của bài thỏa mãn \(\mathbf{m = n - 1}\);

+ Subtask4. Có 10% số test ứng với 10% số điểm của bài không có ràng buộc bổ sung.