/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
N 頂点 M 辺の単純有向グラフが与えられます。 頂点には 1 から N までの番号が、辺には 1 から M までの番号がそれぞれ付けられており、辺 j は頂点 U_j から頂点 V_j に向かって伸びています。 各頂点には得点と呼ばれる整数値が定まっており、頂点 i の得点は P_i です。 また、各辺には減衰率と呼ばれる 0 以上 1 以下の実数値が定まっており、辺 j の減衰率は W_j です。 なお、与えられるグラフには有向閉路が存在しないことが保証されます（すなわち、ある頂点 i からいくつか辺を辿って再び頂点 i に戻ってくる方法は存在しません）。
高橋君はこのグラフ上でゲームをしようとしています。 最初、頂点 1 にコマが 1 つおいてあり、高橋君のスコアは 0 です。 高橋君は、今から以下のように操作を行うことで、コマを頂点 N まで動かしながらスコアを増やしていきます。
- 現在コマが置いてある頂点の番号を i とする。頂点 i の得点 P_i をスコアに加算する。
- i=N ならばゲームを成功として終了する。
- 頂点 i から伸びている辺が存在しないならば、ゲームを失敗として終了する。そうでないならば、頂点 i から伸びている辺を 1 本選ぶ。
- 選んだ辺の番号を j とする。各頂点の得点に辺 j の減衰率をかける。すなわち、各 i\ (1\leq i\leq N) に対して P_i \leftarrow P_i\times W_j とする。
- コマを頂点 V_j に動かし、1. に戻る。
高橋君がゲームを成功として終了させることが可能かどうか判定し、可能ならばゲーム終了時におけるスコアの最大値を求めてください。
制約
- N,M,P_i,U_j,V_j は整数
- 2\leq N \leq 10^5
- 1\leq M \leq 10^5
- 1\leq P_i\leq 10^4
- U_j \neq V_j
- (U_j,V_j)\neq (U_k, V_k)\ (j\neq k)
- 0\leq W_j\leq 1
- W_j は 10^{-6} の倍数であり、小数点以下第 6 位まで与えられる
- 与えられるグラフに有向閉路は存在しない
入力
入力は以下の形式で標準入力から与えられる。
N M P_1 P_2 \dots P_N U_1 V_1 W_1 U_2 V_2 W_2 \vdots U_M V_M W_M
出力
高橋君がゲームを成功として終了させることが可能ならばゲーム終了時におけるスコアの最大値を、不可能ならば -1 を出力せよ。
なお、前者の場合、真の値との絶対誤差または相対誤差が 10^{−6} 以下であれば正解として扱われる。
入力例 1
4 4 2 5 3 1 1 3 0.500000 1 2 0.250000 2 3 0.250000 3 4 0.500000
出力例 1
3.7500000000
以下、数列 (P_1,P_2,P_3,P_4) のことを簡単に P と表記します。 最初、P=(2,5,3,1) です。
コマを頂点 1\rightarrow 3\rightarrow 4 と動かすとき、ゲームは以下のように進行します。
- 頂点 1 の得点 P_1=2 をスコアに加算する。
- 頂点 1 から伸びている辺のうち辺 1 を選ぶ。
- 各頂点の得点に辺 1 の減衰率 W_1=0.5 をかける。P=(1,2.5,1.5,0.5) になる。
- コマを頂点 V_1=3 に動かす。
- 頂点 3 の得点 P_3=1.5 をスコアに加算する。
- 頂点 3 から伸びている辺のうち辺 4 を選ぶ。
- 各頂点の得点に辺 4 の減衰率 W_4=0.5 をかける。P=(0.5,1.25,0.75,0.25) になる。
- コマを頂点 V_4=4 に動かす。
- 頂点 4 の得点 P_4=0.25 をスコアに加算する。
- ゲームを成功として終了する。
このとき、ゲーム終了時におけるスコアは 2+1.5+0.25=3.75 となり、これが最大値です。
入力例 2
3 1 1 1 1 1 2 0.000000
出力例 2
-1
ゲームを成功として終了させることはできません。
入力例 3
6 12 22 75 26 45 72 81 4 6 0.185514 3 6 0.758252 2 3 0.622989 2 4 0.984614 1 3 0.465086 1 5 0.396959 5 3 0.618272 5 2 0.016128 1 2 0.869673 1 4 0.363219 2 6 0.097935 5 4 0.877468
出力例 3
138.6258141601
Problem Statement
You are given an N-vertex M-edge simple directed graph. The vertices are numbered 1 through N, and the edges are numbered 1 through M. Edge j directs from vertex U_j to vertex V_j. Each vertex has an integer attribute point: the point of vertex i is P_i. Also, each edge has a real attribute decay between 0 and 1: the decay of edge j is W_j. It is guaranteed that the given graph does not have a closed cycle. (In other words, there is no way to travel from a vertex i along edges to go back to vertex i.)
Takahashi is going to play a game on this graph. Initially, vertex 1 has a piece on it, and Takahashi's score is 0. He performs the following procedure to move the piece to vertex N while accumulating his score.
- Let i be the current number of vertex with the piece. Add the point P_i of vertex i to his score.
- If i=N, he ends the game successfully.
- If there is no edge going from vertex i, he ends the game unsuccessfully. Otherwise, choose an edge going from vertex i.
- Let j be the number of the chosen edge. Multiply the point of each vertex by the decay of edge j. In other words, let P_i \leftarrow P_i\times W_j for each i\ (1\leq i\leq N).
- Move the piece to vertex V_j, and jump to step 1.
Determine if he can end the game successfully. If it is possible, print the maximum possible final score of the game.
Constraints
- N,M,P_i,U_j, and V_j are integers.
- 2\leq N \leq 10^5
- 1\leq M \leq 10^5
- 1\leq P_i\leq 10^4
- U_j \neq V_j
- (U_j,V_j)\neq (U_k, V_k)\ (j\neq k)
- 0\leq W_j\leq 1
- W_j is a multiple of 10^{-6} and given with six decimal places.
- The given graph does not have a directed cycle.
Input
The input is given from Standard Input in the following format:
N M P_1 P_2 \dots P_N U_1 V_1 W_1 U_2 V_2 W_2 \vdots U_M V_M W_M
Output
Print the maximum possible final score if he can successfully end the game, and -1 otherwise.
In the former case, your answer is considered correct if the absolute or relative error from the true value is at most 10^{−6}.
Sample Input 1
4 4 2 5 3 1 1 3 0.500000 1 2 0.250000 2 3 0.250000 3 4 0.500000
Sample Output 1
3.7500000000
We denote the sequence (P_1,P_2,P_3,P_4) simply by P. Initially, P=(2,5,3,1).
If he moves the piece along vertices 1\rightarrow 3\rightarrow 4, the game proceeds as follows.
- Add the point P_1=2 of vertex 1 to his score.
- Among the edges going from vertex 1, choose edge 1.
- Multiply the point of each vertex by the decay W_1=0.5 of edge 1. Now, P=(1,2.5,1.5,0.5).
- Move the piece to vertex V_1=3.
- Add the point P_3=1.5 of vertex 3 to his score.
- Among the edges going from vertex 3, choose edge 4.
- Multiply the point of each vertex by the decay W_4=0.5 of edge 4. Now, P=(0.5,1.25,0.75,0.25).
- Move the piece to vertex V_4=4.
- Add the point P_4=0.25 of vertex 4 to his score.
- He ends the game successfully.
In this case, the final score is 2+1.5+0.25=3.75, which is maximum possible.
Sample Input 2
3 1 1 1 1 1 2 0.000000
Sample Output 2
-1
He cannot end the game successfully.
Sample Input 3
6 12 22 75 26 45 72 81 4 6 0.185514 3 6 0.758252 2 3 0.622989 2 4 0.984614 1 3 0.465086 1 5 0.396959 5 3 0.618272 5 2 0.016128 1 2 0.869673 1 4 0.363219 2 6 0.097935 5 4 0.877468
Sample Output 3
138.6258141601