コマが頂点 \(1\) から辺 \(e_1,e_2,\dots,e_k\) をこの順に通って頂点 \(N\) まで移動することを考えます。すなわち、全ての \(1\leq i< k\) について \(V_{e_i}=U_{e_{i+1}}\) であり、\(U_{e_1}=1,V_{e_k}=N\) です。このとき、ゲーム終了時のスコア \(\mathrm{score}(e_1,\dots,e_k)\) は以下の式で表されます。

\[ \mathrm{score}(e_1,\dots,e_k) = P_{U_{e_1}}+W_{e_1}P_{U_{e_2}}+\dots +\left(\prod_{i=1}^{k-1}W_{e_i}\right)P_{U_{e_k}} +\left(\prod_{i=1}^{k}W_{e_i}\right)P_N \]

ここで、任意の辺 \(e\) に対して、関数 \(f_{e}\) を \(f_{e}(x)=W_e\times x+P_{U_e}\) で定めます。すると、スコアは以下のように表せます。

\[\mathrm{score}(e_1,\dots,e_k) = (f_{e_1} \circ f_{e_2} \cdots \circ f_{e_k})(P_N) =f_{e_1}(f_{e_2}(\cdots (f_{e_k}(P_N))))\]

これは単に式変形をすることでも示せますが、より直観的には、この問題は操作を逆順に見ることで以下の問題（＊）に変換されることを言っています。

最初コマが頂点 \(N\) にあり、スコアは \(P_N\) である。辺をさかのぼる向きにコマを繰り返し動かすことで、コマを頂点 \(1\) まで移動させる。ある辺 \(e\) を通ってコマをある頂点 \(v\) に動かすと、現在のスコアを \(s\) として、この操作後のスコアは \(W_e\times s+P_v\) になる。最終的なスコアの最大値はいくつか。

この言い換えの嬉しいところは、元の問題では（何度か操作を行って到達した）ある状態を表すのに「今いる頂点」「現在のスコア」「今までに通った辺の減衰率の総積」が必要であり、特に最後の要素が実数値であるため動的計画法への帰着が困難であったのが、変換後の問題（＊）ではある状態を表すのに「今いる頂点」「現在のスコア」だけで事足りるため、容易に動的計画法の枠組みに落とし込めるようになったことです。

実際に、以下のような動的計画法を考えることができます。

\(\mathrm{dp}[v]=\) 変換後の問題（＊）においてコマを頂点 \(N\) から頂点 \(v\) まで移動させたいとき、最終的なスコアの最大値

遷移については、貰う DP を考えて、コマを頂点 \(v\) に移動させる直前のコマの位置を全探索すればよいです。具体的には、頂点 \(v\) から伸びている各辺 \(e\) に対し \(\mathrm{dp}[v]\leftarrow \max(\mathrm{dp}[v],f_e(\mathrm{dp}[V_e]))\) とすればよいです。

実装については、頂点 \(1\) から初めてメモ化再帰で DP テーブルを埋めていくと簡潔です。頂点 \(N\) までの有向パスが存在しないような頂点の扱いに注意してください。

計算量は \(O(N+M)\) です。

実装例 (C++) :

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> p(n);
    for (int &i: p) cin >> i;
    vector<vector<pair<int, double>>> G(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        double w;
        cin >> u >> v >> w;
        --u, --v;
        G[u].emplace_back(v, w);
    }
    vector<double> dp(n, -1);
    vector<bool> seen(n);
    auto calc_dp = [&](auto &calc_dp, int u) -> void {
        if (seen[u]) return;
        seen[u] = true;
        if (u == n - 1) {
            dp[u] = p[u];
            return;
        }
        for (auto [v, w]: G[u]) {
            calc_dp(calc_dp, v);
            if (dp[v] != -1) dp[u] = max(dp[u], dp[v] * w + p[u]);
        }
    };
    calc_dp(calc_dp, 0);
    if (dp[0] != -1) cout << fixed << setprecision(10) << dp[0] << endl;
    else cout << -1 << endl;
}