想定解より良いオーダーだったので書きます
まず、元のグラフについて、そのノードを通る確率を前から計算していきます。
ノード番号の若いほうから以下の図のような遷移をすると可能です。
今度は、「そのノードからあと何ノードたどればゴールできるかの期待値」も計算してみましょう。これは右側(頂点番号)の大きい方から探索していきます。
最後に、それぞれの辺に着目して、その辺を消すと「そのノードからゴールまでの手数の期待値」がどのくらい改善されるのかにそのノードに入る確率を掛けたものが全体の改良幅となるので、それの最小をとったものが解です。
計算量ですが、どのステップでも各辺に対して1度の操作を行うことになるので\(O(M)\)です。
