Change background image
Chuyên Tin - Lê Khiết

Go downThông điệp [Trang 1 trong tổng số 1 trang]

© FMvi.vn

on Sat Dec 22, 2012 10:36 pm
Admin

Code - Huyền Thoại

1782. Xây cầu

Mã bài: BRIDGES

Đất nước Delta là quốc đảo lớn trên thế giới. Đất nước gồm N đảo nhỏ được đánh số từ 1 đến N. Việc đi lại giữa các đảo là rất khó khăn. Vì kinh tế còn rất kém phát triển, nhà nước phải khó khăn lắm mới mở được N – 1 tuyến phà biển để người dân người dân có thể đi lại được giữa hai đảo bất kì. Cách đây không lâu, đất nước mới nhận được sự đầu tư lớn của các nước tư bản. Nhà vua quyết định xây mới K cây cầu để thay cho K tuyến phà. Các cây cầu mới được xây dựng sẽ nối liền hai đảo mà trước đây có tuyến phà nối trực tiếp. Nhà vua muốn tính toán để chọn K tuyến phà nào để xây thành cầu sau cho tổng thời gian để đi lại giữa mọi cặp đỉnh là nhỏ nhất. Tức là: đạt giá trị nhỏ nhất. Trong đo TA B là thời gian đi từ đảo A đến đảo B. Bạn hãy giúp nhà Vua tính toán chọn ra K trong số N - 1 tuyến phà để thay thế bằng cầu.

Input

Dòng thứ nhất ghi 4 số nguyên N, K, VP, VC trong đó VP là vận tốc nếu đi bằng phà và VC là vận tốc nếu đi bằng cầu. VP và VC có đơn vị là m/s
N – 1 dòng tiếp theo, mỗi dòng ghi 3 số U V L thể hiện giữa đảo U và đảo V đã có một tuyến phà, và khoảng cách giữa U và V là L mét.
Output

In ra K số là số hiệu của tuyến phà cần được thay thế bằng cầu.

Giới hạn

1 ≤ K < N ≤ 10 000
1 ≤ VP, VC ≤ 100 000
1 ≤ LU V ≤ 106
Thời gian: 1s/test
Example

Input:
6 2 1 2
1 2 5
3 2 6
1 4 4
4 6 4
4 5 5

Output:
1 3
http://chuyentinlk.123.st

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà Admin
Trả lời nhanh

Về Đầu TrangThông điệp [Trang 1 trong tổng số 1 trang]

  © FMvi.vn

|_-Diễn Đàn Tin Học - Lê Khiết-_|

« Xem bài trước | Xem bài kế tiếp »

Bài viết liên quan

    Quyền hạn của bạn:

    Bạn không có quyền trả lời bài viết