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

NKCITY - Xây dựng thành phố

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/nkcity


Nước Anpha đang lập kế hoạch xây dựng một thành phố mới và hiện đại. Theo kế hoạch, thành phố sẽ có N vị trí quan trọng, được gọi là N trọng điểm và các trọng điểm này được đánh số từ 1 tới N. Bộ giao thông đã lập ra một danh sách M tuyến đường hai chiều có thể xây dựng được giữa hai trọng điểm nào đó. Mỗi tuyến đường có một thời gian hoàn thành khác nhau.

Các tuyến đường phải được xây dựng sao cho N trọng điểm liên thông với nhau. Nói cách khác, giữa hai trọng điểm bất kỳ cần phải di chuyển được đến nhau qua một số tuyến đường. Bộ giao thông sẽ chọn ra một số tuyến đường từ trong danh sách ban đầu để đưa vào xây dựng sao cho điều kiện này được thỏa mãn.

Do nhận được đầu tư rất lớn từ chính phủ, bộ giao thông sẽ thuê hẳn một đội thi công riêng cho mỗi tuyến đường cần xây dựng. Do đó, thời gian để hoàn thành toàn bộ các tuyến đường cần xây dựng sẽ bằng thời gian lâu nhất hoàn thành một tuyến đường nào đó.

Yêu cầu: Giúp bộ giao thông tính thời gian hoàn thành các tuyến đường sớm nhất thỏa mãn yêu cầu đã nêu.

Dữ liệu

Dòng chứa số N và M (1 ≤ N ≤ 1000; 1 ≤ M ≤ 10000).

M tiếp theo, mỗi dòng chứa ba số nguyên u, v và t cho biết có thể xây dựng tuyến đường nối giữa trọng điểm u và trọng điểm v trong thời gian t. Không có hai tuyến đường nào nối cùng một cặp trọng điểm.

Kết quả

Một số nguyên duy nhất là thời gian sớm nhất hoàn thành các tuyến đường thỏa mãn yêu cầu đã nêu.

Ví dụ

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

Kết quả
3

Được gửi lên bởi:Jimmy
Ngày:2008-12-09
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:PTNK Team Selection 2008

hide comments
2011-08-28 09:28:09 **** U
Cây Khung nhỏ nhất phải ko nhỉ
2011-03-20 15:07:14 Nguyễn Phúc Bình Nguyên
@Thảo: bài này là bài oi thì chấm đúng bao nhiêu test sẽ cho điểm theo %. 100 tương đương đúng hết. Đạt yêu cầu là các bài chấm đúng hết+không quá thời gian, tương đương bạn được 100 bài dạng oi.
2011-03-09 09:36:59 Huỳnh Quang Thảo
cho mình hỏi: mình chạy được 0,11s và mem là 218kb, nhưng mà nó báo là 100 chứ không phải là đat yêu cầu, vậy nó có giống nhau không? nếu khác thì mình sai chỗ nào vậy?. mình mới tham gia diễn đàn, mọi người thông cảm.
2010-11-30 12:44:39 Dra Tiny
Prim chứ
2009-08-26 07:02:06 loc_konoko
bai nay so khong lon lam, duyet DFS van AC.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.