bzoj#P2306. [Ctsc2011]幸福路径

[Ctsc2011]幸福路径

题目描述

有向图 GGnn 个顶点 1,2,,n1, 2, \ldots , n,点 ii 的权值为 wiw_i。现在有一只蚂蚁,从给定的起点 v0v_0 出发,沿着图 GG 的边爬行。开始时,它的体力为 11。每爬过一条边,它的体力都会下降为原来的 ρ\rho 倍,其中 ρ\rho 是一个给定的小于 11 的正常数。而蚂蚁爬到某个顶点时的幸福度,是它当时的体力与该点权值的乘积。我们把蚂蚁在爬行路径上幸福度的总和记为 hh。很显然,对于不同的爬行路径,hh 的值也可能不同。小 Z 对 hh 值的最大可能值很感兴趣,你能帮助他计算吗?注意,蚂蚁爬行的路径长度可能是无穷的。

输入格式

每一行中两个数之间用一个空格隔开。输入文件第一行包含两个正整数 n,mn, m,分别表示 GG 中顶点的个数和边的条数。第二行包含 nn 个非负实数,依次表示 nn 个顶点权值 w1,w2,,wnw_1, w_2, \ldots , w_n。第三行包含一个正整数 v0v_0,表示给定的起点。第四行包含一个实数 ρ\rho,表示给定的小于 11 的正常数。接下来 mm 行,每行两个正整数 x,yx, y,表示 <x,y><x, y>GG 的一条有向边。可能有自环,但不会有重边。

输出格式

仅包含一个实数,即 hh 值的最大可能值,四舍五入到小数点后一位。

5 5
10.0 8.0 8.0 8.0 15.0
1
0.5
1 2
2 3
3 4
4 2
4 5
18.0

数据规模与约定

对于 100%100\% 的数据,n100 n \leq 100m1000m \leq 1000ρ1106\rho \leq 1 – 10^{-6}wi100 (i=1,2,,n)w_i \leq 100 \ (i = 1, 2, \ldots , n)

题目来源

Day1