Di chuyển hai chế độ

General
Points
68
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved