Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

CHAMPORD - Ճամփորդություն

Գրաֆլանդիայի N քաղաքներն իրար միացված են N - 1 երկկողմանի մայրուղիներով այնպես, որ կամայական քաղաքից մեկ այլ քաղաք տանող ճիշտ մեկ ճանապարհ կա: Գրաֆլանդիայում երթևեկության կանոնները խիստ են։ i-րդ մայրուղին ունի Li երկարություն և  այդ մայրուղով պետք է երթևեկել այնպիսի հաստատուն արագությամբ, որ ծախսվի ճիշտ Ti ժամանակ: Դա հարմար է. խցանումներ չեն առաջանում։

Բայց տուրիստը չի ուզում արագ երթևեկել։ Նա ցանկանում է ընտրել K + 1 հատ քաղաք պարունակող ճանապարհ այնպես, որ այդ ճանապարվով երթևեկելիս նրա միջին արագությունը լինի հնարավորինս փոքր:

Տրված են N, K թվերը և բոլոր մայրուղիների նկարագրությունները, պետք է հաշվել տուրիստի հնարավոր ամենափոքր միջին արագությունը:

Մուտք

Մուտքի առաջին տողում տրված են N և K թվերը: Հաջորդ N - 1 տողերից յուրաքանչյուրում տրված է մի մայրուղու նկարագրություն: Մայրուղին նկարագրվում է u, v, l, t ամբողջ թվերի քառյակով, որը նշանակում է, որ այն միացնում է u և v քաղաքները, մայրուղու երկարությունը l է, իսկ այն հատելու ժամանակը՝ t (1 ≤ u ≤ N, 1 ≤ v ≤ N,  0 ≤ l ≤ 104, 0 ≤ t ≤ 104, 0 ≤ K < N, N ≤ 20000):

Թեստերի 50%-ում N≤1000:

Ելք

Արտածել խնդրի պատասխանը 10-6 ճշտությամբ:

Օրինակ

Մուտքը.
4 2
1 2 7 2
2 4 4 6
2 3 4 3 Ելքը. 0.8888889

Ավելացրեց.Andreasyan
Ամսաթիվ.2014-04-05
Ժամանակի սահմանափակումը.0.100s-1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.C CSHARP C++ 4.3.2 CPP CPP14 JAVA PAS-GPC PAS-FPC PYTHON3
Աղբյուրը.Հանրապետական 2014

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.