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.|

CAPITAL - Thủ đô

 

Đất nước Megaland rộng lớn có địa hình hiểm trở, giao thông đi lại khá khó khăn. N thành 

phố ở quốc gia này (được đánh số từ 1 đến N) phân bố rải rác khắp đất nước. Hệ thống giao thông cả 

nước chỉ gồm N-1 đoạn đường, mỗi đoạn đường này là đường đi hai chiều nối trực tiếp hai thành phố 

nào đó.  Thú vị là ở chỗ, chỉ với các đoạn đường đó, cư dân từ mỗi thành phố đều có thể đến được bất 

kỳ thành phố nào khác trong đất nước rộng lớn này.

Với việc thủ đô hiện tại là thành phố P (1 ≤ P ≤ N), chính quyền Megaland nhận thấy có

những thành phố khác phải mất một chặng đường dài tới K mile (mile - một đơn vị tính chiều dài 

được sử dụng tại đây) để đến được thủ đô và điều này đã gây không ít ảnh hưởng đến sự phát triển 

của đất nước. Bởi vậy, chính quyền có dự định thực hiện một dự án theo đó sẽ chọn một thành phố Q 

thích hợp (1 ≤ Q ≤ N, Q ≠ P) để nâng cấp thành một đơn vị hành chính ngang tầm thủ đô (xem như là 

thủ đô thứ hai). Nếu dự án được thực hiện thì từ thành phố bất kỳ, chỉ mất một chặng đường không 

quá L mile để đến được một trong hai thủ đô P hoặc Q. 

Giới đầu tư cho dự án quan tâm đến mức độ hiệu quả của dự án là bao nhiêu nếu hiệu quả này 

được đặc trưng bởi hiệu số M = K - L.

 

Yêu cầu : Xác định giá trị lớn nhất của M

Dữ liệu vào:

- Dòng thứ nhất ghi số nguyên N (3 ≤ N ≤ 10000) và số P

- N-1 dòng tiếp theo, mỗi dòng ghi ba số nguyên I, J, D với ý nghĩa: có đoạn đường nối 

trực tiếp hai thành phố I, J và chiều dài đoạn đường này là D mile (1 ≤ I, J ≤ N, 1 ≤ D ≤ 106)

 

Kết quả: Ghi ra  số M tìm được.

 

Ví dụ: 

Input :

10 2 

10 3 2 

10 4 1 

4 2 9 

9 5 4 

6 2 8 

7 10 8 

9 10 7 

8 6 1 

1 10 5

Output :

10 

 

 Ràng buộc :

- Có 40% số test ứng với 40% số điểm của bài ứng với N ≤ 100. 

- Có 60% số test ứng với 60% số điểm của bài ứng với N ≤ 1000. 

- Có 80% số test ứng với 80% số điểm của bài ứng với N ≤ 5000. 

 
Đất nước Megaland rộng lớn có địa hình hiểm trở, giao thông đi lại khá khó khăn. N thành 
phố ở quốc gia này (được đánh số từ 1 đến N) phân bố rải rác khắp đất nước. Hệ thống giao thông cả 
nước chỉ gồm N-1 đoạn đường, mỗi đoạn đường này là đường đi hai chiều nối trực tiếp hai thành phố 
nào đó.  Thú vị là ở chỗ, chỉ với các đoạn đường đó, cư dân từ mỗi thành phố đều có thể đến được bất 
kỳ thành phố nào khác trong đất nước rộng lớn này. 
Với việc thủ đô hiện tại là thành phố P (1  P  N), chính quyền Megaland nhận thấy có 
những thành phố khác phải mất một chặng đường dài tới K mile (mile - một đơn vị tính chiều dài 
được sử dụng tại đây) để đến được thủ đô và điều này đã gây không ít ảnh hưởng đến sự phát triển 
của đất nước. Bởi vậy, chính quyền có dự định thực hiện một dự án theo đó sẽ chọn một thành phố Q 
thích hợp (1  Q  N, Q  P) để nâng cấp thành một đơn vị hành chính ngang tầm thủ đô (xem như là 
thủ đô thứ hai). Nếu dự án được thực hiện thì từ thành phố bất kỳ, chỉ mất một chặng đường không 
quá L mile để đến được một trong hai thủ đô P hoặc Q. 
Giới đầu tư cho dự án quan tâm đến mức độ hiệu quả của dự án là bao nhiêu nếu hiệu quả này 
được đặc trưng bởi hiệu số M = K - L. 
 
Yêu cầu: Xác định giá trị lớn nhất của M. 
Dữ liệu: Được cho trong file CAPITAL.INP có cấu trúc như sau: 
  Dòng thứ nhất ghi số nguyên N (3  N  10000) và số P. 
  N-1 dòng tiếp theo, mỗi dòng ghi ba số nguyên I, J, D với ý nghĩa: có đoạn đường nối 
trực tiếp hai thành phố I, J và chiều dài đoạn đường này là D mile (1  I, J  N, 1  D  
10
6
).  
Kết quả: Ghi ra file CAPITAL.OUT số M tìm được. 
Ví dụ: 
CAPITAL.INP  CAPITAL.OUT 
10 2 
10 3 2 
10 4 1 
4 2 9 
9 5 4 
6 2 8 
7 10 8 
9 10 7 
8 6 1 
1 10 5 
10 
 
 Ràng buộc:  
  Có 40% số test ứng với 40% số điểm của bài ứng với N ≤ 100. 
  Có 60% số test ứng với 60% số điểm của bài ứng với N ≤ 1000. 
  Có 80% số test ứng với 80% số điểm của bài ứng với N ≤ 5000. 

 

 


Được gửi lên bởi:Kata
Ngày:2014-04-14
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ừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:Olympic 30/4/2014 Tp.Hồ Chí Minh

hide comments
2018-04-09 15:34:25
bài này còn khó hơn cả bài thi thử voi 2018 đợt 2 bài kia chặt np còn ra chứ bài này chịu
2017-03-14 16:03:06
ây za 10p cho 60đ :)
2016-03-30 19:03:52 thantung
dfs + it
2015-03-15 16:29:29 ♡Angelo♡
bài này ai có tư tưởng chỉ e với.
xuantruong98happy@gmail.com
2014-06-17 04:34:51 thu
ai giải được bài này cho mình ý tưởng với!
2014-04-21 12:52:32 Thcs Ðặng Chánh Kỷ
mình hiểu đề rồi chạy test ví dụ rồi mà sao chấm toàn 0 hầy ai ac rồi có thể cho thử 2 3 test mình chạy kiểm tra đc không
2014-04-20 17:50:52 Thcs Ðặng Chánh Kỷ
không hiểu đề cho lắm
2014-04-17 02:18:28 Thỏ con làm bánh
Còn time limit 1s nữa chớ :|
2014-04-17 02:17:10 Thỏ con làm bánh
Nghĩ sao mà chấm trên server cũ vậy má =.=
2014-04-15 10:17:07 Mew.
K = 21, chọn Q là đỉnh 10 => L = 11 => M = 10
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.