P4308 [CTSC2011] Happy Path

There is a directed graph $G$ with $n$ vertices $1, 2, \cdots, n$, and the weight of vertex $i$ is $w(i)$. An ant starts from a given starting vertex $v_0$ and crawls along the edges of $G$. Initially, its stamina is $1$. Each time it traverses an edge, its stamina is multiplied by $\rho$, where $\rho$ is a given positive constant less than $1$. When the ant reaches a vertex, its happiness is the product of its current stamina and the weight of that vertex. We denote the total happiness along the crawling path by $H$. Clearly, for different crawling paths, the value of $H$ may differ. Xiao Z is interested in the maximum possible value of $H$. Can you help compute it? Note that the length of the ant’s path may be infinite.

Numbers on each line are separated by a single space. The first line contains two positive integers $n, m$, the number of vertices and edges in $G$. The second line contains $n$ non-negative real numbers, representing the vertex weights $w(1), w(2), \cdots, w(n)$. The third line contains a positive integer $v_0$, the given starting vertex. The fourth line contains a real number $\rho$, the given positive constant less than $1$. Each of the next $m$ lines contains two positive integers $x, y$, indicating that $(x, y)$ is a directed edge of $G$. Self-loops may exist, but there are no multiple edges.

Output a single real number: the maximum possible value of $H$, rounded to one decimal place.

For $100\%$ of the testdata, $1 \leq n \le 100$, $1 \leq m \le 1000$, $0 < \rho \le 1 - 10^{-6}$, $0 \leq w(i) \leq 100$. Translated by ChatGPT 5