DQUERY - Khảo sát đường đua
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

Nếu ở Việt Nam, chúng ta có tổ chức hội trọi trâu thì ở bang Wiscosin nước Mỹ, bác nông dân John hay tổ chức những cuộc thi chạy maratong cho những chú bò của mình. Bác có N cánh đồng, N cánh đồng này được nối với nhau bằng N – 1 con đường nhỏ. Bác John cần chọn hai cánh đồng để làm nơi xuất phát và đích đến. Qua khảo sát các điều kiện đơn giản ban đầu, bác đã chọn được K cặp. Bây giờ bạn cần tính toán độ dài của K đường đua này để bác John lựa chọn một đường đua hợp lý nhất.

Dữ liệu: 

- Dòng 1 ghi số N.

- Dòng 2 đến N mỗi dòng ghi 3 số ui vi wi.

- Dòng N + 1 ghi số K.

- Dòng N + 2 đến N + K + 1 ghi K cặp số.

Kết quả: 

- Gồm K dòng, mỗi dòng ghi một số là độ dài đường đua

Giới hạn:

- 1 ≤ N ≤ 80000

- 1 ≤ K ≤ 100000

- 1 ≤ Wi ≤ 10000

Ví dụ

  • input
    7
    1 6 13
    6 3 9
    3 5 7
    4 1 3
    2 4 20
    4 7 2
    3
    1 6
    1 4
    2 6
    output
    13
    3
    36
Back to Top