\(S\) から \(T\) への最短パスを一つ固定し、これを \(P\) とします。また、\(P\) の長さを \(X\) とします。

[1] \(S,T\) を除く \(P\) 上の頂点に次数が \(3\) 以上の頂点がある時

\(S,T\) を除く \(P\) 上の頂点にある次数が \(3\) 以上の頂点と結ばれており、 \(P\) 上にない頂点を一つ \(U\) とすると、以下の方法で \(2X+2\) 回の操作で目的が達成できます。

• コマ A を \(S\) から \(U\) に移動させる。
• コマ B を \(T\) から \(S\) に移動させる。
• コマ A を \(U\) から \(T\) に移動させる。

以降は \(2X+1\) 回以下で目的が達成できるかを考えます。

コマ A,B の両方が \(P\) 上の頂点を全て通る場合、明らかに \(2X+2\) 回以上の操作が必要です。

コマ A,B の両方が \(P\) 上の頂点で通らない頂点がある場合は片方が \(P\) 上の頂点を順に通るようにすることで操作回数を減らすことができます。

コマ A,B の片方のみが \(P\) 上の頂点を全て通る場合、もう片方は \(P\) の次に短い \(S\) から \(T\) へのパス \(Q\) を通るとして良いです。これは、 \(Q\) に含まれて \(P\) に含まれない頂点を一つ \(U\) とすると上と同じ移動が可能だからです。この移動により \(X+|Q|\) 回での移動が可能なので、 \(|Q|\le X+1\) を満たすパス \(Q\) が存在するかが分かれば良いです。ここで、 \(|Q|\le X+1\) という条件下では \(P\) の次に短いパスと \(P\) の次に短い道は一致するので、普通の BFS に「最短パスに含まれない辺を通ったか」のパラメータを付与した \(2N\) 頂点での BFS を行うことで \(|Q|\) を求めることができます。

[2] \(S,T\) を除く \(P\) 上の頂点の次数が全て \(2\) の時

\(P\) 上の辺を全て通らないパスの長さの最小値を \(Y\) とすると、 [1] と同じ議論で \(X+Y\) 回の操作で目的を達成することができます。以降は \(X+Y\) 回未満で目的を達成できるか考えます。

\(S\) から \(T\) を経由せずに到達できる次数が \(2\) でない頂点のうち最も近い頂点を \(S'\) 、\(T\) から \(S\) を経由せずに到達できる次数が \(2\) でない頂点のうち最も近い頂点を \(T'\) とします。 \(S',S,T,T'\) はこの順に並んでいます。

もし \(S',T'\) の次数がどちらも \(1\) なら答えは -1 になるので、以降は少なくとも一方の次数が \(3\) 以上であるとします。

対称性より、

• \(S'\) の次数は \(3\) 以上
• \(T'\) の次数が \(3\) 以上なら、\(S\) から \(S'\) までの距離は \(T\) から \(T'\) までの距離以下である

が満たされているとします。また、このときの \(S\) から \(S'\) までの距離を \(Z\) とします。

\(X+Y\) 回未満で目的を達成するためには、コマ A,B の両方が \(P\) を通って移動する必要があります。

\(S'\) から \(T\) までは一本道であるため、目的を達成するためには両方 \(S'\) より奥に移動させる必要があり、少なくとも \(2X+4Z+4\) 回の操作が必要であることが分かります。しかし、\(S'\) と結ばれた頂点のうち \(S'\) から \(T\) のパスに含まれない頂点を \(U_1,U_2\) と取ると

• コマ A を \(S\) から \(U_1\) に移動させる。 \(Z+1\) 回の操作が必要。
• コマ B を \(T\) から \(U_2\) に移動させる。 \(X+Z+1\) 回の操作が必要。
• コマ A を \(U_1\) から \(T\) に移動させる。 \(X+Z+1\) 回の操作が必要。
• コマ A を \(U_2\) から \(S\) に移動させる。 \(Z+1\) 回の操作が必要。

として実際に移動させることができるため、\(2X+4Z+4\) 回という上界は達成可能です。

\(T\) で同じことをしても少なくとも \(2X+4Z+4\) 回以上かかるので、 \(2X+4Z+4\) と \(X+Y\) の小さい方が答えとなります。

[3] まとめ

以上をまとめると、以下のようになります。

• 最短パスが複数ある場合は \(2X\) が答え。
• 上以外の状況で、長さ \(X+1\) のパス（道）が存在する場合は \(2X+1\) が答え。
• 上以外の状況で、最短パス上に次数 \(3\) 以上の頂点が存在する場合は \(2X+2\) が答え。
• 上以外の状況では以下の \(2\) つの最小値が答え。
  • 与えられたグラフから最短パスに含まれる辺を全て除いたグラフにおける \(S\) から \(T\) の最短距離を \(Y\) とした時の、 \(X+Y\)
  • 頂点 \(S,T\) から次数 \(3\) 以上の頂点までの距離の最小値を \(Z\) とした時の、 \(2X+4Z+4\)

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(N+M)\) です。

実装例(Python3)