公式解説にて最短経路問題に帰着された際のコスト関数は、 \(A\) の単調性より Monge 性を持ちます。

よってこの問題はMonge グラフ上での単一始点最短路問題に帰着することができ、これはオンライン・オフライン変換を用いることで \(O(N \log^2 N)\) や \(O(N \log N)\) 時間で解くことができます。