歷史課有好幾條規定,稱不上是不合理,但很惱人。這也讓歷史課成為班上學生不怎麼喜歡的課程之一。
- 不可以使用 3C 產品
- 不可以睡覺
- 吃飯要去教室外面吃
- 不可以比老師晚到,遲到要在黑板上畫圈圈並記上時間
- 要做一些報告,通常需要花好幾個小時
然而,這並不影響歷史這一科其實很有趣的事實,如果不考試的話。除了推敲每個時期發生了什麼,以及它為什麼發生,學習歷史中我們常常可以發現一些很好玩的巧合:
- 牛津大學在宋朝就成立了
- 慈禧太后大概用的是愛迪生公司的供電系統和燈泡
- 麥當勞在二戰期間創立
你會發現,這種通常平常不會想到的巧合正是因為我們缺乏橫向連結。所以,我們給定很多事件,希望求所有事件到彼此之間最短的時間差。
然而,哆拉A夢在這時候出現了並拿出了如果電話亭。
「如果,這世界上的加法全部變成乘法...」
「啊啊啊不行!會壞掉的!啊啊啊!」
然而,在撥打完後,因為本身的運算也從加法變成乘法了,所以哆拉A夢和如果電話亭都壞掉了。你知道,如果要將哆拉A夢和如果電話亭修好就必須要讓事件之間產生連結。一般來說需要耗用大量能量,而耗用能量最少的辦法...
「不就是我們剛剛做的所有事件彼此之間最短的時間距離嗎?」
然而,並沒有這麼簡單,因為年份也變得混亂,所以我們能得到的只有兩個事件之間的評估值。而更遠的點之間的評估值,我們用一連串的評估值相乘得到,例如:
A-5-B-2-C
AB 之間評估值為 5, BC 之間評估值 2,則 AC 間的評估值為 $5 \times 2 = 10$。而如果有多條可能路徑,我們取最小值。例如:
A-5-B-2-C
| |
----7----
AC 之間評估值為 7。
你可以幫幫他們,把哆啦A夢修好嗎?
第一行有兩個數 $N, M, Q$ ,代表有 $N$ 個編號 $1$~$N$ 的事件和 $M$ 條事件之間的評估值與 $Q$ 筆詢問。
接下來有 M 行,每行有三個數 $u, v, w$ ,分別代表編號 $u, v$ 之間的評估值為 $w$
接下來有 $Q$ 行,每行有二個數 $u, v$,請輸出u到v的最短距離的以十為底的對數,即$log_{10}(dis(u,v))$
$N \le 1500$
$M \le 3000$
$Q \le 100000$
$1 \le u,v \le N$
$1 \le w \le 10{18}$
保證圖連通
對於每次詢問,請輸出$log_{10}(dis(u,v))$
輸出的答案與真正的答案絕對誤差在 $10 ^ {-6}$ 內皆視為正確
3 3 1 1 2 5 2 3 2 1 3 7 1 3
0.845098040014256813
4 4 3 1 2 1 1 3 100 2 3 100 3 4 10000 2 3 1 4 2 4
2 6 6
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~9 | $n \le 20, m\le 100,q \le 100, w=10$ | 10 |
| 2 | 10~19 | $n\le 500, m\le 1000, q \le 10000$ | 20 |
| 3 | 20~29 | $w=10 ^ x, 0\le x\le 18$ | 20 |
| 4 | 0~39 | 無其他限制 | 50 |