AtCoder Beginner Contest 144：F - Fork in the Road

問題
解法
解答

問題

https://atcoder.jp/contests/abc144/tasks/abc144_f

解法

M 本の辺それぞれをふさいだときの E を計算していては O(M^2) となり間に合わない．ここで，ある頂点 v から出る辺のうち 1 つを塞ぐとするとき，v とつながる先の頂点から頂点 N までの経路数が最も多いような辺を塞ぐのが最適．各頂点から頂点 N までの経路数は簡単な DP で求めることが出来るから，この DP を全ての v (1 <= v <= N) について実行し，E の最小値を答えにすればよい．各 DP が O(N + M) であるから，全体で O(N(N + M))．