• محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • منبع: آزمون عملی دوره ۲۴ المپیاد کامپیوتر

زمستان سردی است و بارش سنگین برف، باعث مسدود شدن را‌ه‌ها شده‌ است. آقای مهندس برای یک پروژه‌ی کاری به شهر 1 رفته و قصد دارد به خانه‌اش که در شهر شماره‌ی nn قرار دارد باز‌گردد. او در هر روز می‌تواند در شهری که هست بماند و یا یکی از جاده‌های غیر‌مسدود متصل به آن شهر را طی کند. آقای مهندس اطلاعات بسیار مفیدی از سازمان‌ هواشناسی کسب کرده و احتمال مسدود بودن هر جاده را می‌داند. دقت کنید که مسدود بودن یک جاده در یک روز، مستقل از مسدود بودن یا نبودن آن، در روز‌های قبل‌اش است. برای نمونه، اگر احتمال مسدود بودن یک جاده را pp بگیریم، احتمال این که جاده دو روز متوالی مسدود باشد، p2p^2 و احتمال این‌که در هیچ‌کدام از دو روز بسته نباشد، (p1)2(p-1)^2 است. عبور از هر جاده دقیقا یک روز طول می‌کشد.

حال اگر آقای مهندس قصد داشته باشد در کمترین زمان به خانه‌اش برسد و برای رسیدن به این هدف کاملا هوشمندانه عمل کند، امید‌ریاضی تعداد روز‌هایی که طول می‌کشد تا او به خانه باز‌گردد، چقدر است.

ورودی

در سطر اول ورودی دو عدد طبیعی nn، تعداد شهر‌ها، و mm، تعداد جاده‌ها، آمده است.

هر کدام از mm سطر بعدی شامل سه عدد طبیعی uu و vv و pp است که به معنای وجود یک جاده‌ی دوطرفه با احتمال مسدود بودن p/1000p/1000 بین دو شهر uu و vv است.

تضمین می‌شود که گراف شهر‌های داده‌شده همبند است.

بین هر دو شهر حداکثر یک جاده وجود دارد و هیچ‌ شهری به خودش جاده ندارد.

احتمال مسدود بودن تمامی جاده‌ها کمتر از ۱ است.

2n100 000 2 \le n \le 100\ 000 1m100 000 1 \le m \le 100\ 000 1u,vn 1 \le u , v \le n uv u \ne v 0p1 000 0 \le p \le 1\ 000

خروجی

در تنها سطر خروجی امید‌ریاضی تعداد روز‌هایی که آقای مهندس در راه است را با دقیقن ۳ رقم اعشار چاپ کنید.

زیرمسئله‌ها

زیرمسئله نمره محدودیت
۱ ۵ گراف شهر‌ها درخت است.
۲ ۵۵ n1 500 n \le 1\ 500 و حداکثر چهار جاده به هر شهر وصل است
۳ ۱۵ n300 n \le 300
۴ ۲۵ بدون محدودیت اضافی

مثال

ورودی نمونه ۱

4 4
1 2 500
1 3 500
2 4 625
3 4 500
Plain text

خروجی نمونه ۱

3.556
Plain text

ورودی نمونه ۲

2 1
1 2 999
Plain text

خروجی نمونه ۲

1000.000
Plain text

(۲۴امین دوره المپیاد کامپیوتر - آزمون سوم - ۱۳۹۳/۰۶/۰۶)


ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.