yukicoder 1364 Road to Cherry from Zelkova
まず与えられた有向グラフをトポロジカルソートしておく.
もしトポロジカルソートができない, すなわちグラフに閉路がある場合は長さの総和は無限になる(なぜなら閉路で無限に長さを稼ぐことができるからである).
そうでない場合, DAG上でDPをすることによって解くことができる. 具体的には次のようにDPをしていけばよい.
$ dp_i := 頂点$ 0から頂点$ iまでの歩道の個数, $ dp2_i := 頂点$ 0から頂点$ iまでの歩道の長さの総和
今いる頂点を$ v, 遷移先の1つを$ cとおく.
$ dp_c = dp_c + dp_v \cdot a_{v→cのindex}
$ dp2_c = dp2_c + dp2_v \cdot a_{v→cのindex} + dp_v \cdot l_{v→cのindex} となる.
遷移はトポロジカル順に行えばよい. 計算量は$ O(N + M)となる.