h839: 磷酸距離
Tags : DP 圖論 最短路徑
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Special

最近更新 : 2022-04-12 22:18

Content

背景

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

阿祁:怎麼辦,我只會出水題…嗚嗚嗚

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}$

Input

每筆測資第一行有三個數代表$N$$M$$K$ 代表他的節點數量、邊的數量以及$K$的值,接著有$M$行,每行三個數代表$U_i$$V_i$$W_i$,也就是邊的兩端的節點以及他的權重。對於所有輸入保證至少有條路徑連接$1、N$

Output

輸出最小的磷酸距離 $\sum_{i = 1}^{p}\frac{C_i}{X_i}$本題容許在1以內的誤差

Sample Input #1
4 4 3
1 3 1
1 2 2
3 4 3
1 4 6
Sample Output #1
2
Sample Input #2
5 4 10
1 2 1
2 3 2
3 4 3
4 5 4
Sample Output #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
Hint :

前面五筆測資保證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}$

Tags:
DP 圖論 最短路徑
出處:
Chi's Coding Problem [管理者:
linlincaleb@... (臨末之頌)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」