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

NKTRAFIC - Monkey island

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274825/problem/Y
{assign var="code" value="NKTRAFIC"} {if $par==""} {assign var=par value=$locale} {/if}
{if $par=="vn"} {literal}

Sau khi phân chia đất nước thành các thành phố, đảo khỉ lại nảy sinh vấn đề mới: phải ngăn chặn việc vận chuyển chuối! Đảo khí có N thành phố đánh số từ 1 đến N nối với nhau bởi M đường nối hai chiều. Giữa hai thành phố có nhiều nhất một con đường. Giữa hai thành phố bất kỳ có ít nhất một đường đi (tạo bởi một hoặc nhiều con đường). Đảo khỉ có hai thủ đô là thành phố 1 và thành phố N.

Gần đây, việc vận chuyển chuối giữa hai thủ đô tăng vọt. Để tấn công việc vận chuyển, tổng thống huy động G binh lính, mỗi binh lính có thể đặt tại vị trí bất kỳ trên một con đường, có thể gần thành phố tùy ý, nhưng không được nằm trong thành phố. Trong trường hợp có lệnh tấn công vào một trong hai thủ đô, tất cả binh lính phải di chuyển đến thủ đô đó. Các binh lính di chuyển với vận tốc không đổi. Thời gian cần thiết để huy động một cuộc tấn công như vậy bằng khoảng cách lớn nhất từ các binh lính đến một trong hai thủ đô.

Yêu cầu: xác định một cách bố trí các binh lính sao cho mọi đường đi từ thủ đô này đến thủ đô kia đều đi qua ít nhất một con đường có binh lính gác và thời gian huy động tấn công trong trường hợp xấu nhất là nhỏ nhất.

Dữ liệu

  • Dòng đầu tiên chứa 3 số nguyên N, M, G cách nhau bởi khoảng trắng.
  • Mỗi dòng trong số M dòng sau chứa 3 số nguyên a, b, c cách nhau bởi khoảng trắng, cho biết có một đường nối hai chiều giữa thành phố a và b với độ dài c.

Kết qủa

In ra một số nguyên duy nhất là thời gian nhỏ nhất để tất cả các binh lính có thể di chuyển đến một thủ đô, với đúng một chữ số thập phân. Nếu không có lời giải, in ra -1.

Giới hạn

  • 2 < N < 155
  • 2 < M < 5055
  • 0 < độ dài của một con đường < 1024
  • 2 < G < 4096

Ví dụ

Dữ liệu:
6 6 2
1 2 1
2 3 2
3 6 1
1 4 1
4 5 3
5 6 1

Kết qủa
2.5
{/literal}{elseif ($par=="en" || $par=="")}{literal}

After they divided the country into counties the monkeys have a new problem: they have to stop the banana traffic. Monkey Land has N cities numbered from 1 to N connected by M two-directional roads. Between each two cities there is at most one road but between any to cities there is at least one connecting path (made up of one ore more roads). Cities 1 and N are capitals.

Lately, the banana traffic between the two capitals has increased. In order to fight the traffic the president has G soldiers he can place anywhere on a road, no matter how close to a city, but not inside a city. In case of an attack on one of the capitals all soldiers must get to that capital. Soldiers move at the same constant speed. The amount of time required for such a mobilization is equal to the maximum distances from the soldiers to one of the capitals.

Task

Write a program that finds a soldier placement solution so that any path from one capital to the other go through at least one road with a soldier and the mobilization time for the worst case scenario be minimal.

Input

The input contains on the first line three integers N M G separated by blanks.

Each of the following M lines contains three integers separated by blanks a b c meaning "there is a two-way road between city a and b of length c".

Output

The output will contain a single line with the minimum time needed for all the soldiers to get to a capital, written with one exact decimal. If there is no solution, the first line will contain -1.

Constraints

  • 2 < N < 155
  • 2 < M < 5055
  • 0 < the length of any road < 1024
  • 2 < G < 4096

Example

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

Output
2.5
{/literal} {/if}

Được gửi lên bởi:Jimmy
Ngày:2008-01-06
Thời gian chạy:0.108s
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:Campion 2005

hide comments
2013-07-15 17:38:32 Âu Vãn Thịnh
bài này ghe giống tìm đường đi ngắn nhất ko biết có phải ko ?
2011-11-12 09:11:35 NTT
jh
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.