Đèn giao thông tại ngã tư

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