VM 10 Bài 12 - Tăng tốc mạng máy tính

Xem dạng PDF

Gửi bài giải


Điểm: 0,26 (OI)
Giới hạn thời gian: 0.38s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
VM10 - Tác giả: Cosmin Gheorghe
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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!

Input

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.

  • ~1 \le N \le 1000~
  • ~1 \le M \le 10^{5}~
  • ~1 \le K \le 10~
  • ~1 \le c \le 10^{6}~

Output

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.

Sample Input

5 5 2
1 2 1
2 3 9
3 5 1
1 4 5
4 5 5

Sample Output

4.25

Note

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.


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.