Bài 4: Xe cứu thương (3 điểm)

Một thành phố có ~N~ điểm dân cư đánh số từ 1 đến ~N~, được kết nối bởi ~M~ con đường hai chiều.

Con đường thứ ~i~ nối từ điểm ~u_i~ đến điểm ~v_i~, có độ dài là ~w_i~ (đơn vị độ dài) và thời gian di chuyển là ~t_i~ (đơn vị thời gian)
~(1 ≤ u_i, v_i ≤ N; 1 ≤ w_i, t_i ≤ 100; i = 1, 2, 3, …, M)~.

Xe cứu thương (chạy điện) có thể di chuyển từ điểm dân cư này sang tất cả các điểm dân cư khác thông qua các con đường trên. Khi có yêu cầu, xe cứu thương ở vị trí hiện tại sẽ di chuyển tới điểm nhân và đưa tới bệnh viện phù hợp. Theo thông số kỹ thuật, pin của xe không cho phép di chuyển quá ~L~ (đơn vị độ dài).

Trung tâm điều phối nhận được thông tin và giao nhiệm vụ cho ~Q~ xe khác nhau.
Xe cứu thương thứ ~j~ đang ở vị trí ~X_j~ được giao nhiệm vụ tới điểm ~Y_j~ đón bệnh nhân rồi đưa tới bệnh viện ở điểm ~Z_j~
~(~Xj, Yj, Z_j ≤ N~; ~j = 1, 2, 3, …, Q~).

Yêu cầu

Với mỗi xe cứu thương, hãy xác định thời gian di chuyển ngắn nhất để xe đó có thể tới đón và đưa bệnh nhân tới bệnh viện mà không cần phải dừng lại để sạc pin.

Dữ liệu vào

Vào từ file RESCUE.INP:

• Dòng đầu tiên chứa 3 số nguyên dương ~N~, ~M~, ~L~
  ~(N ≤ 100; M ≤ 1000; L < 1024)~.
• ~M~ dòng tiếp theo, dòng thứ ~i~ ~(i = 1, 2, 3, …, M)~ chứa 4 số nguyên
  ~u_i, v_i, w_i, t_i~ xác định con đường thứ ~i~.
• Dòng tiếp theo chứa số nguyên dương ~Q~.
• ~Q~ dòng cuối, dòng thứ ~j~ ~(j = 1, 2, 3, …, Q)~ chứa 3 số nguyên dương
  ~X_j, Y_j, Z_j~ xác định vị trí và nhiệm vụ của xe thứ ~j~.

Kết quả

Ghi ra file RESCUE.OUT gồm ~Q~ dòng.
Dòng thứ ~j~ là thời gian di chuyển ngắn nhất để xe thứ ~j~ đi đón và đưa bệnh nhân tới bệnh viện.

• Biết thời gian đưa bệnh nhân lên xe không đáng kể.
• Trường hợp xe bắt buộc phải dừng lại sạc pin thì in ra -1.

Ví dụ

RESCUE.INP

4 5 21
1 4 10 3
4 2 6 9
1 2 20 10
2 3 5 2
1 3 7 9
3
1 1 2
3 2 1
4 1 2

RESCUE.OUT

10
13
-1

Giải thích

• Xe thứ nhất đang ở điểm dân cư 1, đón bệnh nhân ở chính điểm đó rồi đi trực tiếp tới 2.
• Xe thứ hai đi theo lộ trình: ~3 → 2 → 3 → 1~.
  Không thể đi ~3 → 2 → 1~ do không đủ pin.
• Xe thứ ba không thể thực hiện được do không đủ pin.

Subtasks

• Subtask 1 (0.9 điểm):
  ~Q ≤ 100~, ~L = 1~, ~X_j = Y_j~, ~j = 1, 2, 3, …, Q~
• Subtask 2 (1.2 điểm):
  ~Q ≤ 100~, ~L = 2~
• Subtask 3 (0.6 điểm):
  ~Q ≤ 5~

• Subtask 4 (0.3 điểm):
  ~Q ≤ 10^4~

  Tài liệu tham khảo