Di chuyển hai chế độ
Points
68
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho $N$ địa điểm và $M$ con đường hai chiều. Mỗi con đường nối $u, v$ có thời gian đi bộ là $a$ và thời gian đi xe buýt là $b$. Bạn xuất phát tại đỉnh $1$ trong trạng thái đi bộ. Tại bất kỳ đỉnh nào, bạn có thể đổi từ đi bộ sang đi xe buýt với chi phí thời gian là $S$, hoặc đổi từ xe buýt sang đi bộ miễn phí (mất $0$ thời gian). Hãy tìm thời gian nhỏ nhất để đi đến đỉnh $N$, hoặc -1 nếu không đến được.
Dữ liệu vào
- Dòng đầu chứa ba số nguyên $N, M, S$ ($1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$, $0 \le S \le 10^9$).
- $M$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $u, v, a, b$ ($1 \le u, v \le N$, $0 \le a, b \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là thời gian nhỏ nhất để đến $N$, hoặc
-1.
Ví dụ
| Input | Output |
|---|---|
| 3 2 5 1 2 10 2 2 3 10 2 |
9 |
| 3 1 4 1 2 3 1 |
-1 |
Giới hạn
- $1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$
- $0 \le S, a, b \le 10^9$
Community Discussion