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

NETACCEL - Tăng tốc mạng máy tính

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274823/problem/D
https://codeforces.com/group/FLVn1Sc504/contest/272622/problem/I

Cho mạng máy tính gồm N máy và M liên kết hai chiều giữa các máy. Các máy được đánh số từ 1 đến N. Máy của Bờm là máy 1 còn máy của Cuội là máy N. Mỗi đường nối cần tốn một giá trị thời gian khác nhau để dữ liệu truyền qua. Tốc độ kết nối giữa hai máy là độ dài đường truyền dữ liệu ngắn nhất giữa hai máy đó.

Tốc độ kết nối của mạng khá chậm khiến Bờm và Cuội không thể chơi Dota được, do đó Bờm quyết định mua K thiết bị tăng tốc mạng. Thiết bị tăng tốc mạng được gắn vào các đường truyền dữ liệu giữa hai máy. Mỗi thiết bị sẽ làm giảm thời gian truyền dữ liệu của đường truyền đi một nửa.

Hãy giúp Bờm đặt các thiết bị tăng tốc sao cho tốc độ kết nối giữa máy của Bờm và Cuội là nhanh nhất có thể để hai bạn có thể chơi Dota mà không bị lag!

Dữ liệu

Dòng đầu chứa 3 số N, M, K.

M dòng tiếp theo, mỗi dòng chứa 3 số x, y, c mô tả một đường truyền dữ liệu: x, y là số hiệu của hai máy tính, còn c là thời gian truyền dữ liệu.

Giới hạn

  • 1 <= N <= 1000
  • 1 <= M <= 100,000
  • 1 <= K <= 10
  • 1 <= c <= 1,000,000

Kết quả

In ra 1 số duy nhất là tốc độ kết nối nhanh nhất có thể sau khi đã lắp đặt các thiết bị tăng tốc, làm tròn đến 2 chữ số thập phân.

Ví dụ

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

Kết quả
4.25

Giải thích

Bờm lắp cả 2 thiết bị tăng tốc lên đường nối giữa máy 2 và máy 3.


Được gửi lên bởi:Jimmy
Ngày:2010-06-30
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ừ: GOSU PERL6 PYPY RUST SED
Nguồn bài:VM10 - Tác giả: Cosmin Gheorghe

hide comments
2019-11-09 03:23:02
Cảm ơn anh CBG_K28, em sai giống y anh, chỉnh float thành double là được :)
2019-08-11 19:03:02
2 đấm AC
2019-06-05 16:32:12
trâu cũng ac :)
2019-05-29 14:38:18
3 đấm mới AC. do để kiểu float thế là 90đ, thay bằng double cái AC ngay
from CBG_K28
2019-01-23 14:20:10
https://ideone.com/lLm73x
code c++
2017-11-12 10:15:53
9 đấm AC :D
vq
2017-10-30 17:12:38
Bellman Ford + Deque + tính trước mảng lũy thừa = AC
2017-08-08 06:38:47
quên không làm tròn đến 2 chữ số thập phân, mất mất lần nộp
2017-03-31 14:54:33
maxN=1000 mà ghi 100...
10 đấm AC.........................
2016-10-01 18:50:21
cả năm ms lên spoj làm bt 1 lần mà đọc đề bài này xong lại muốn chơi game ++
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.