Hệ thống giao thông của thành phố có N nút giao thông đánh số 1,2,3,... với M tuyến
đường nối trực tiếp hai chiều.
Bờm xuất phát từ nút giao thông 1 ở thời
điểm 0 và cần di chuyển tới nút giao thông N trong thời gian nhanh nhất. Tuy nhiên, hiện tại
đang là thời kì kiểm soát an ninh gắt gao nên tại mỗi nút giao thông, có thể có
những thời điểm bị chặn chiều đi để kiểm tra hành chính, và thời điểm rời đi phải
chuyển sang thời điểm không bị chặn sớm nhất sau đó.
Chẳng hạn, nếu Bờm ở nút 2 ở thời điểm
3, muốn di chuyển đến nút 4 trong khoảng thời gian 5 thì Bờm sẽ tới nút 4 ở thời
điểm 8, tuy nhiên nếu 2 bị chặn chiều ở thời điểm 3, Bờm phải chờ đến thời điểm
4 mới đi được, nếu vẫn bị chặn, Bờm phải chờ đến thời điểm 5, … Các nút giao
thông không bị chặn chiều đến.
Cho thông tin về các tuyến đường và các
thời điểm bị chặn của mỗi nút giao thông, hãy xác định thời điểm Bờm có thể đến
N sớm nhất.
Dữ liệu: vào
từ file WST.INP:
· Dòng 1: hai
số nguyên N, M (2<=N<=10^5; 0<M<=10^5)
· Dòng 2 …M+1:
mỗi dòng ba số nguyên u, v, t (u<>v; 1<=t<=10^4) thể hiện một tuyến đường nối hai nút u, v tốn
thời gian di chuyển t. Các tuyến đường là hai chiều và giữa hai nút bất kì có
không quá một tuyến đường nối trực tiếp chúng.
·
Dòng M+2 … M+N+1: dòng M+2+i ghi thông tin về
nút giao thông i, bắt đầu bằng số nguyên C là số thời điểm bị chặn, tiếp theo
là C số nguyên không âm theo trật tự tăng chỉ các thời điểm nút i bị chặn. Dữ
liệu đảm bảo tổng số lượng thời điểm bị chặn của toàn hệ thống không vượt quá
105.
Kết quả: đưa
ra file wst.out
·
Ghi số nguyên duy nhất là thời điểm Bờm đến N
sớm nhất có thể, số này bằng -1 nếu Bờm
không có cách di chuyển tới N.
Ví dụ:
|
WST.INP
|
WST.OUT
|
giải thích
|
|
4
6
2 4 5
1 3 3
3 4 3
1 4 8
2 3 4
1 2 2
0
1 3
2 3 4
0
|
7
|
Từ
1, Bờm có thể:
+
Đi trực tiếp tới 4, tốn thời gian 8
+
Đi tới 3, đến 3 ở thời điểm 3, ở đó các thời điểm 3, 4 bị chặn, Bờm chỉ có thể
xuất phát từ 3 ở thời điểm 5, do đó cũng đến 4 ở thời điểm 8
+
Đi tới 2 ở thời điểm 2, thời điểm này 2 không bị chặn nên Bờm có thể đi ngay
đến 4, tốn thời gian 5; cách này cho thời điểm đến 4 là 7.
|
