h839. 磷酸距離 - 高中生程式解題系統

內容

背景

阿祁每次都被臨末嘲諷，因為臨末太電了，不過最近他有個計畫，他想出一題難題來考倒臨末，然而這似乎有點困難。

阿祁：怎麼辦，我只會出水題…嗚嗚嗚

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}}$ 最小，請試著找到這個值，保證答案 $\leq 10^{6}$ 。

測資範圍

$1 \leq N, M \leq 500$

$m i n (N - 1, M) \leq K \leq 1000$

$1 \leq U_{i}, V_{i} \leq N$

$1 \leq W_{i} \leq 10^{5}$

$a n s \leq 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以內的誤差。

範例輸入 #1

範例輸出 #1

範例輸入 #2

範例輸出 #2

3.833333

測資資訊：

記憶體限制： 512 MB
公開測資點#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。

範例說明:

範例一圖長這樣，其中以路線 $1 - > 4$ 最好，令 $X = (3)$ ，則磷酸距離為 $(6 / 3) = 2$ 。另外考慮另一條路線 $1 - > 3 - > 4$ ，令 $X = (1, 2)$ 可以得到這條路線之最小值 $(1 / 1) + (3 / 2) = 2.5$ ，但這不是這題的最小值。

答對的判斷標準:這題利用 $S p e c i a l J u d g e$ ，只要 $| 你的答案 - 測資答案 | <= 1$ 皆會 $A C$ 。，例如答案是1而你輸出0.88453會 $A C$ 。，但是你若輸出2.10002就會 $W A$ 。

標籤:

DP 圖論最短路徑

出處:

Chi's Coding Problem [管理者： linlincaleb@gmail.com

linlincaleb@ ... (臨末之頌) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」