背景
阿祁每次都被臨末嘲諷，因為臨末太電了，不過最近他有個計畫，他想出一題難題來考倒臨末，然而這似乎有點困難。
阿祁：怎麼辦，我只會出水題…嗚嗚嗚
Ststone：我聽說臨末不會圖論題哈哈
lai alan：我好像也有聽說過這件事，只是不知道是不是真的
神秘人物：是真的吧，他每次CF遇到圖論都燒雞
阿祁：好欸，那出題了！
題目敘述
給你一個$N$個點(編號$1$ ~ $N$)、$M$個邊的無向簡單圖，以及一正整數$K$，對於第$i$個邊，有個連結$U_i$、$V_i$且權重為$W_i$的雙向邊，請你考慮每個以$1$為起點、$N$ 為終點、途中不經過重複點之路徑，假設某個路徑經過了$p$個邊，則我們把這$p$個邊的權重以$C_1,\ C_2,\ C_3,\ ... ,\ C_p$的方式表示，接著我們要決定一個長度為$p$的正整數序列$X_1,\ X_2,\ X_3,\ ... ,\ X_p$，使得$\sum_{i = 1}^{p}X_i=K$，現在我們想讓$\sum_{i = 1}^{p}\frac{C_i}{X_i}$的值越小越好(注意這可能是浮點數)，這個值我們稱做磷酸距離，簡單來說就是要你找條路徑、以及長度和經過邊的數量相等的序列$X$，使得$\sum_{i = 1}^{p}\frac{C_i}{X_i}$最小，請試著找到這個值，保證答案$\ ≤ 10^6$。
測資範圍
$\color{black}{1 ≤ N, M ≤ 500}$
$\color{black}{min(N-1, M) ≤ K ≤ 1000}$
$\color{black}{1 ≤ U_i, V_i ≤ N}$
$\color{black}{1 ≤ W_i ≤ 10^5}$
$\color{black}{ans ≤ 10^6}$
每筆測資第一行有三個數代表$N$、$M$、$K$ 代表他的節點數量、邊的數量以及$K$的值，接著有$M$行，每行三個數代表$U_i$、$V_i$、$W_i$，也就是邊的兩端的節點以及他的權重。對於所有輸入保證至少有條路徑連接$1、N$。
輸出最小的磷酸距離 $\sum_{i = 1}^{p}\frac{C_i}{X_i}$，本題容許在1以內的誤差。
4 4 3 1 3 1 1 2 2 3 4 3 1 4 6
2
5 4 10 1 2 1 2 3 2 3 4 3 4 5 4
3.833333
公開 測資點#0 (12%): 0.5s , <1K
公開 測資點#1 (12%): 0.5s , <1K
公開 測資點#2 (12%): 0.5s , <1K
公開 測資點#3 (12%): 0.5s , <1K
公開 測資點#4 (13%): 0.5s , <1K
公開 測資點#5 (13%): 2.0s , <1M
公開 測資點#6 (13%): 2.0s , <1M
公開 測資點#7 (13%): 2.0s , <1M
前面五筆測資保證N<50。
範例說明:
範例一圖長這樣，其中以路線$\color{black}{1->4}$最好，令$\color{black}{X=(3)}$，則磷酸距離為$\color{black}{(6/3)=2}$。另外考慮另一條路線$\color{black}{1->3->4}$，令$\color{black}{X=(1,2)}$可以得到這條路線之最小值$\color{black}{(1/1)+(3/2)=2.5}$，但這不是這題的最小值。
答對的判斷標準:這題利用$Special\ Judge$，只要$|你的答案-測資答案|<=1$皆會$\color{lime}{AC}$。，例如答案是1而你輸出0.88453會$\color{lime}{AC}$。，但是你若輸出2.10002就會$\color{red}{WA}$。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||