在游戲《星際爭霸 II》中,戰(zhàn)列巡航艦作為人類的終極作戰(zhàn)武器,在后期 以及一些中期戰(zhàn)術(shù)中發(fā)揮著空中堡壘的作用,其 “戰(zhàn)術(shù)跳躍” 技能能讓其在游戲 中期在敵軍基地上空造成打擊之后在血量較低時(shí)撤離,進(jìn)行無戰(zhàn)損騷擾,在人 類 vs 異蟲對抗中經(jīng)常用來壓制異蟲中期的發(fā)展。
你在玩一個(gè)游戲,游戲中有 n 個(gè)地點(diǎn)和 m 條單向時(shí)空航道。每條時(shí)空航道形如 (u, v, w, x),其中 u,v 表示這條時(shí)空航道的起點(diǎn)終點(diǎn),w 表示通過這條航道需要的時(shí)間(注意這個(gè)時(shí)間是現(xiàn)實(shí)當(dāng)中游戲者的時(shí)間也是游戲內(nèi)的時(shí)間),x表示這條航道使用的頻繁程度。時(shí)空航道不會成環(huán),但可能會有兩條航道的起別為x ,x ,x ,···x,那么選擇第i個(gè)航道的概率就是∑ xi 。你的目的是在L 123 k kj=1xj點(diǎn)相同同時(shí)終點(diǎn)也相同。游戲開始的時(shí)候,你的戰(zhàn)列巡航艦到達(dá)了地點(diǎn) 1,每當(dāng)你到達(dá)一個(gè)地點(diǎn)的時(shí)候,戰(zhàn)艦的電腦會按照每個(gè)起點(diǎn)為該地點(diǎn)的時(shí)空航道的頻繁程度隨機(jī)選擇一個(gè)航道并花費(fèi) w 單位時(shí)間到達(dá)該航道的終點(diǎn)。具體來說,對于一個(gè)時(shí)間點(diǎn) u,假如有 k 個(gè)起點(diǎn)為該地點(diǎn)的時(shí)空航道,他們的頻繁程度分別為x ,x ,x ,···x,那么選擇第i個(gè)航道的概率就是∑ xi 。你的目的是在L 123 k kj=1xj單位游戲時(shí)間內(nèi)到達(dá)一個(gè)沒有任何以該地點(diǎn)為起點(diǎn)的時(shí)空航道的地點(diǎn)。當(dāng)然你 可以在到達(dá)某一個(gè)地點(diǎn)時(shí)重新開始游戲,如果你重新開始這個(gè)游戲,你就能回 到游戲開始的那一刻(即 1 號地點(diǎn))并重置游戲內(nèi)的時(shí)間(即你又可以有 L 單 位的時(shí)間去跳躍了),你也可以在沒有任何以該地點(diǎn)為起點(diǎn)的地點(diǎn)重新開始,且 無次數(shù)限制。你需要最小化你在現(xiàn)實(shí)中花費(fèi)的時(shí)間。當(dāng)然在你運(yùn)氣足夠好的情 況下,你一定可以達(dá)成游戲目標(biāo)。
保證一定有至少一條以 1 號地點(diǎn)為起點(diǎn)的航道。 請閱讀樣例以更清晰地理解題意。
第一行三個(gè)正整數(shù) n,m,L。
接下來 m 行,每行四個(gè)正整數(shù) u,v,w,x。
(2 ≤ n ≤ 100,1 ≤ m ≤ 200,w, x ≤ 100,0 ≤ L ≤ 109)
一行一個(gè)浮點(diǎn)數(shù)表示答案,令你的答案為 a,標(biāo)準(zhǔn)答案為 b,如果滿足 |a?b|/max(1,b) ≤ 10?9(即絕對誤差或者相對誤差不超過 10?9)即為正確。
3 2 3 1 2 2 1 1 2 4 1
6
2019年精選賽題 2299 2300 2301 2302 2304 2305 2306 2307 2308 2310 2311 2312
2299 2300 2301 2302 2304 2305 2306 2307 2308 2310 2311 2312
2299 2300 2301 2302 2304 2305 2306 2307 2308 2310 2311 2312