(writer解では)ないです。

概説

道を頂点、橋を辺としたグラフを考えて、BFSやDijkstraで解けるように見えるだろう。

実際にBFSで解けることを確認する。

条件がいくつかあるが、\(X_i=Y_i \neq X_j(1 \leq i < j \leq M)\)とすれば全ての条件を満たすことがわかるだろう。

このとき、全ての橋を設置するには、全ての橋に対して次の操作のいずれかを行えばよい。

• 勇者一行が道\(_l\)の位置\(p\)にいるときに、\(A_i,B_i \neq l\)であるような道\(_i\)を位置\(p\)に設置する。
• 勇者一行が道\(_l\)の位置\(p\)にいるときに、\((A_i,B_i)=(l,k)\)であるような道\(_i\)をに設置して、勇者一行が道\(_k\)の位置\(p+1\)に移動する。

ここでBFSなどの方法で、道を頂点、橋を辺としたグラフにおける、道\(_1\)から道\(_G\)までの最短経路を求めたとして、その経路を通るように、全ての橋を設置できることを確認する。

• 道\(_1\),道\(_G\)を通るものの場合

  道\(_1\)に接続しない全ての橋を設置する。

  道\(_1\)と、道\(_G\)を接続する橋を設置して道\(_G\)に移動する。

  道\(_G\)に接続しない全ての未設置の橋を設置する。

  道\(_1\)と道\(_G\)を接続する橋は制約より\(1\)つしかないため、これで全ての橋を設置できる。

• 道\(_{l_1}\),,,道\(_{l_k}\),道\(_G\)を通るものの場合(\(l_1=1\)とする。)

  \(i=1\)として、\(i<n-2\)まで、道\(_{l_i}\)と道\(_{l_{i+1}}\)を接続するコスト最小の橋を設置して道\(_l_{i+1}}\)に移動して、\(i\)を\(1\)増加させる。

  道\(_{l_k}\)と道\(_G\)を接続するコスト最小でない全ての橋を設置する。

  道\(_{l_{k-1}}\)と道\(_{l_k}\)を接続するコスト最小の橋を設置して道\(_{l_k}\)に移動する。

  道\(_{l_k}\)に接続しない全ての未設置の橋を設置する。

  道\(_{l_k}\)と道\(_G\)を接続する橋を設置して道\(_G\)に移動する。

  道\(_G\)に接続しない全ての未設置の橋を設置する。

  これで全ての橋を設置できる。

よってBFSなどで求めた最短経路の通りに移動できることが確認できた。

よってBFSなどで答えを求めることができる。