Hành Trình Người Sói

Điểm: 1,00 (OI)

Giới hạn thời gian: 3.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Remus Lupin trong hình dạng người sói, cần di chuyển từ khu vực $1$ đến khu vực $N$ trong Rừng Cấm. Rừng Cấm có $N$ khu vực được nối bởi $M$ con đường hai chiều.

Chu kỳ trăng có $T$ pha, đánh số từ $0$ đến $T - 1$ . Tại thời điểm $t$ , pha trăng hiện tại là $t mod T$ . Người sói bắt đầu tại khu vực $1$ ở thời điểm $0$ (pha $0$ ).

Mỗi con đường $i$ nối khu vực $u_{i}$ và $v_{i}$ , có thời gian di chuyển $w_{i}$ đơn vị. Tuy nhiên, con đường chỉ an toàn khi pha trăng hiện tại nằm trong khoảng $[l_{i}, r_{i}]$ . Nếu $l_{i} \leq r_{i}$ , đường an toàn tại các pha $l_{i}, l_{i} + 1, \dots, r_{i}$ . Nếu $l_{i} > r_{i}$ , khoảng quay vòng: đường an toàn tại các pha $l_{i}, l_{i} + 1, \dots, T - 1, 0, 1, \dots, r_{i}$ .

Người sói chỉ có thể bắt đầu đi trên một con đường khi pha trăng hiện tại nằm trong khoảng an toàn. Khi đi trên đường $i$ , thời gian tăng thêm $w_{i}$ và pha trăng khi đến nơi là $(t + w_{i}) mod T$ .

Tại bất kỳ khu vực nào, người sói có thể chờ đợi $1$ đơn vị thời gian (pha trăng tăng lên $1$ ).

Tìm thời gian ngắn nhất để di chuyển từ khu vực $1$ đến khu vực $N$ . In $- 1$ nếu không thể đến được.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên $N$ , $M$ , $T$ .
$M$ dòng tiếp theo, mỗi dòng chứa năm số nguyên $u_{i}$ , $v_{i}$ , $w_{i}$ , $l_{i}$ , $r_{i}$ mô tả một con đường.

Dữ liệu ra

In một số nguyên duy nhất — thời gian ngắn nhất để đi từ khu vực $1$ đến khu vực $N$ , hoặc $- 1$ nếu không thể.

Ràng buộc

$2 \leq N \leq 5 \times 10^{4}$
$1 \leq M \leq 10^{5}$
$1 \leq T \leq 100$
$1 \leq w_{i} \leq 10^{6}$
$0 \leq l_{i}, r_{i} < T$
$1 \leq u_{i}, v_{i} \leq N$ , $u_{i} \neq v_{i}$

Ví dụ

Input	Output	Giải thích
4 4 3 1 2 2 0 1 2 4 3 2 2 1 3 1 0 0 3 4 1 1 1	2	Đi đường 1→3 (w=1, pha 0 hợp lệ, đến pha 1) rồi 3→4 (w=1, pha 1 hợp lệ). Tổng thời gian = 2. Đường 1→2→4 tốn 5 nên không tối ưu.
3 2 4 1 2 1 2 2 2 3 1 3 3	4	Pha 0: đường 1-2 chỉ mở pha 2. Chờ 2 đơn vị (pha 0→1→2), đi 1→2 (w=1, pha 2, đến pha 3). Đường 2-3 mở pha 3, đi ngay 2→3 (w=1). Tổng = 2 + 1 + 1 = 4.

Bình luận

Không có bình luận tại thời điểm này.