Đèn giao thông tại ngã tư
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Một thành phố có $N$ ngã tư (đánh số $1..N$) và $M$ con đường hai chiều, đường thứ $i$ nối $u_i, v_i$ mất $w_i$ giây để đi qua. Tại mỗi ngã tư $u$ có một đèn giao thông hoạt động theo chu kỳ $G_u + R_u$ giây: trong $[0, G_u)$ giây đầu của mỗi chu kỳ đèn màu xanh, trong $[G_u, G_u + R_u)$ giây tiếp theo đèn màu đỏ. Bạn xuất phát từ ngã tư $1$ tại thời điểm $0$. Bạn chỉ có thể rời khỏi một ngã tư $u$ tại thời điểm $t$ nếu đèn tại $u$ đang màu xanh (tức $t \bmod (G_u + R_u) < G_u$); nếu đèn đỏ bạn phải chờ đến khi chuyển xanh. Khi tới ngã tư $N$, bạn dừng lại ngay (không cần đợi đèn ở $N$). Tìm thời gian sớm nhất để đến $N$, hoặc -1 nếu không đến được.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N, M$ ($1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$).
- $N$ dòng tiếp theo, dòng thứ $u$ chứa hai số nguyên $G_u, R_u$ ($1 \le G_u, R_u \le 10^6$).
- $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ ($1 \le u, v \le N$, $1 \le w \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là thời gian sớm nhất đến $N$, hoặc
-1.
Ví dụ
| Input | Output |
|---|---|
| 3 2 3 2 2 3 1 5 1 2 4 2 3 3 |
8 |
| 2 0 2 2 2 2 |
-1 |
Giới hạn
- $1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$
- $1 \le G_u, R_u \le 10^6$, $1 \le w \le 10^9$
Community Discussion