説明の都合上、有向グラフが与えられるものだとします。 (無向辺は有向辺 \(2\) 本に読み替えられます。)

まずは \(C_1 > C_2 > C_3 > \cdots\) を満たす道の重みの総和の最小値を求める問題を考えます。

「今頂点 \(i\) にいて、最後に通った辺は \(j\)」という状態を持ってダイクストラ法を使うことで解くという方針を考えてみましょう。このまま状態を持つと頂点数が \(\Theta(NM)\) になりますが、各頂点 \(i\) について \(j\) として考えられるものは頂点 \(i\) の次数個しかないので、適切に管理すると \(\Theta(M)\) 個になります。辺を愚直に張ってしまうと \(\Theta(N^2)\) 本になってしまうことがありますが、「今頂点 \(i\) にいて、次辺 \(j\) かそれよりも辺の重みが小さい辺を使おうとしている」という状態を新たに導入すると全体で \(\Theta(M)\) 本にすることができます。全体の計算量は \(\Theta(M \log M)\) です。

この問題では \(C_1 < C_2 > C_3 < \cdots\) あるいは \(C_1 > C_2 < C_3 < \cdots\) を満たす道を考えなければいけないのですが、上の問題の解法を少し拡張するだけで解くことができます。全ての状態について、「次の辺の重みは直前の辺の重みより大きくなければいけないか、小さくなければいけないか」という情報を付加します。 (辺を通った回数 mod 2 を持つイメージです。) 全体の計算量は \(\Theta(M \log M)\) です。