Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PWALK - Dạo chơi đồng cỏ

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274829/problem/L

Có N con bò (1 <= N <= 1,000), để thuận tiện ta đánh số từ 1->N, đang ăn cỏ trên N đồng cỏ, để thuận tiện ta cũng đánh số các đồng cỏ từ 1->N. Biết rằng con bò i đang ăn cỏ trên đồng cỏ i.

Một vài cặp đồng cỏ được nối với nhau bởi 1 trong N-1 con đường 2 chiều mà các con bò có thể đi qua. Con đường i nối 2 đồng cỏ A_i và B_i (1 <= A_i <= N; 1 <= B_i <= N) và có độ dài là L_i (1 <= L_i <= 10,000).

Các con đường được thiết kế sao cho với 2 đồng cỏ bất kỳ đều có duy nhất 1 đường đi giữa chúng. Như vậy các con đường này đã hình thành 1 cấu trúc cây.

Các chú bò rất có tinh thần tập thể và muốn được thăm thường xuyên. Vì vậy lũ bò muốn bạn giúp chúng tính toán độ dài đường đi giữa Q (1 <= Q <= 1,000) cặp đồng cỏ (mỗi cặp được mô tả là 2 số nguyên p1,p2 (1 <= p1 <= N; 1 <= p2 <= N).

DỮ LIỆU

  • Dòng 1: 2 số nguyên cách nhau bởi dấu cách: N và Q
  • Dòng 2..N: Dòng i+1 chứa 3 số nguyên cách nhau bởi dấu cách: A_i, B_i, và L_i
  • Dòng N+1..N+Q: Mỗi dòng chứa 2 số nguyên khác nhau cách nhau bởi dấu cách mô tả 1 yêu cầu tính toán độ dài 2 đồng cỏ mà lũ bò muốn đi thăm qua lại p1 và p2.

KẾT QUẢ

  • Dòng 1..Q: Dòng i chứa độ dài đường đi giữa 2 đồng cỏ ở yêu cầu thứ i.

VÍ DỤ

Dữ liệu
4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

Kết quả
2
7

GIẢI THÍCH

Yêu cầu 1: Con đường giữa đồng cỏ 1 và 2 có độ dài là 2. Yêu cầu 2: Đi qua con đường nối đồng cỏ 3 và 4, rồi tiếp tục đi qua con đường nối 4 và 1, và cuối cùng là con đướng nối 1 và 2, độ dài tổng cộng là 7.


Được gửi lên bởi:Jimmy
Ngày:2008-10-22
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:USACO October 2008 - Qualifying Round

hide comments
2015-11-03 13:13:18
DFS or BFS kết hợp danh sách kề mới AC được :(
2015-08-25 14:46:27
THAM KHẢO TẠI https://traitaodo.wordpress.com/2015/08/25/dao-choi-dong-co-pwalk/

Last edit: 2015-10-02 02:27:02
2015-05-19 03:21:22 Thắng Ðam Mê
Dùng dfs vẫn ra, code đơn giản hơn bfs, dùng thêm dsk để giảm đpt thôi
2015-03-30 16:08:10 Vũ Ðức Hùng
1 đấm AC ^^
2015-02-06 12:43:53 Con Bò Huyền Thoại
http://dangminhtien.name.vn/blog/2015/02/06/pwalk-spoj-dao-choi-dong-co/
2014-12-18 16:43:13 Nguyễn Tiến Ðạt
sao n=1000 mà mình làm tìm giống cha chung gần nhất nhưng là thuật toán N^3 mà ko phải N log n sao vẫn ac nhỉ lạ thật.
2014-10-11 15:21:24 Phạm Mạnh Hưng
Yeah! Thêm danh sách kề là được tối đa
Vì giữa 2 đỉnh chỉ có 1 đường đi nên không quan trọng BFS hay DFS :)
2014-09-14 07:53:57 ??? Ares
Floyd 70 LCA AC :3
2014-08-03 17:04:21 ■■‡[ND] Bee Sociu■■‡
trẻ trâu sủa gâu gâu -_-

Last edit: 2015-01-01 16:32:49
2014-07-22 09:49:03 Lãng Tử Lang Thang
Bfs được có 70 điểm thôi à! :((
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.