トポロジカルソートをし、座標が低い順に頂点番号を付け直します。

\(dp[i][j]\) を \(1\) 人が \(i\) 、もう \(1\) 人が \(j\) にいる時の距離の和の最小値と定義します。\((i \leq j)\) とする。

また、\(j\) 以下のチェックポイントは全部通っているものとする。この時、\(dp[i][j]\) の時点で、\(j\) 以下のチェックポイントすべてを通っている必要があるので、高い方の人が直前のチェックポイント以上の位置にいる状態から遷移すれば、必ずどの段階でも \(dp[i][j]\) は \(j\) 以下のチェックポイントを全部通っている。

これは単純に辺から来る人と任意の頂点から来る人を探索すればいいので \(O(NM)\)

実装例(C++)

言いたいことをまとめたツイート