最短経路の個数も一緒に数え上げる最短経路アルゴリズム
ARC 090 E - Avoiding Collision で話題になったこともあり、簡単にメモします。 最短経路を求める DP 的処理をするとき、DAG上のDP だろうと、BFS だろうと、Dijkstra だろうと、以下のような緩和処理をやっています // Edge e の緩和 int dp[MAX_V]; // dp[v] := 始点 s から頂点 v への最短経路長 if (dp[e.to] < dp[e.…
