Elearning CodePath – CTP Online Judge

MRT

31-MRT

🟢 Hard #General #Sorting #Deque

**Time limit: 1s**

Ở Singapore, có $N$ trạm tàu điện được sắp xếp thẳng hàng, được đánh số từ $1$ đến $N$. Sắp tới Ronaldo sẽ tới Singapore du lịch dã dẻ 'cheap'. Có $M$ tuyến tàu điện, mỗi tuyến có đường ray riêng, đánh số từ $1$ đến $M$.
Tuyến tàu thứ $i$ được mô tả bởi 4 số nguyên $A_i, B_i, C_i$ và $D_i$.
Tàu chạy hai chiều giữa hai trạm $A_i$ và $B_i$ (với $A_i < B_i$). Mỗi tuyến phục vụ hai loại tàu:

**1. Tàu thường:**
- Dừng ở tất cả các trạm từ $A_i$ đến $B_i$ (bao gồm cả hai đầu).
- Chi phí đi chuyến từ trạm $x$ đến trạm $y$ (với $A_i \le x, y \le B_i$) là $C_i \times |x - y|$.

**2. Tàu tốc hành:**
- Chỉ dừng ở $A_i$ và $B_i$.
- Chi phí đi chuyến giữa hai trạm này (theo cả hai chiều) là $D_i$.

Để lên tàu, hành khách cần mua vé hành trình với giá $T$ tại trạm xuất phát. Tuy nhiên, nếu chuyển tuyến tại cùng một trạm, bạn không cần mua vé mới. Nếu rời khỏi trạm và muốn tiếp tục hành trình ở trạm tiếp theo, bạn phải mua vé mới. Ngoài ra, có tuyến xe buýt phủ toàn bộ các trạm. Việc di chuyển từ trạm $x$ đến trạm $y$ bằng xe buýt sẽ tốn $K \times |x - y|$. Khách sạn của Ronaldo ở trạm $P$, anh ấy muốn đi từ trạm $P$ đến trạm $Q$ bằng tàu hoặc xe buýt (hoặc kết hợp cả hai). Hãy giúp Ronaldo tìm ra chi phí thấp nhất để thực hiện hành trình này.

### Đầu vào:
- Một dòng gồm 6 số nguyên: $N, M, K, T, P, Q$ (cách nhau bằng dấu cách).
- $M$ dòng tiếp theo, mỗi dòng gồm 4 số nguyên $A_i, B_i, C_i, D_i$ (cách nhau bằng dấu cách).

### Đầu ra:
- In ra chi phí nhỏ nhất cần thiết để đi từ trạm $P$ đến $Q$.

### Ràng buộc:
- $2 \le N \le 100000$
- $1 \le M \le 200000$
- $1 \le K \le 100000$
- $0 \le T \le 100000$
- $1 \le P, Q \le N$
- $1 \le A_i, B_i \le N$
- $1 \le C_i \le 100000$
- $1 \le D_i \le 10^9$

### Subtasks:
- 10% điểm: $A_i=1, B_i=N$
- 20% điểm: $N \le 1000, M \le 5, T=0$
- 20% điểm: $M \le 5$
- 20% điểm: $T=0$
- 30% điểm: Không có ràng buộc bổ sung

### Ví dụ:
**Input:**
10 2 10 1 9 5
7 10 10 8
1 6 8 1
**Output:**
38

✅ Đã AC: 0 / 0 submissions