Description

时间限制: 1 Sec  内存限制: 128 MB
提交: 7  解决: 6
[提交] [状态] [讨论版] [命题人:tkj] [Edit] [TestData]
【题目描述】
一只蚂蚁在一个有向图上面爬，开始体力为1，每爬过一条边体力就*ρ，经过一个点获得点权*体力的收益，求最大收益。 
【输入】
第一行：n和m，表示顶点数和边数。
第二行：n个数，表示每个点的点权。
第三行：一个数，表示起点。
第四行：ρ(0<ρ<1)
接下来m行，每行两个数，描述每条有向边。
【输出】
一个实数，表示最大收益，保留1位小数。
【样例输入】
5 5
10.0 16.0 6.0 12.0 17.0
5
0.7
4 5
1 3
4 2
2 2
4 3
【样例输出】
17.0
【提示】
n<=100
m<=1000
ρ<=1e-6
【来源/分类】tkj