以下では，島 \(i\) と島 \(j\) の距離を，\(dist(i, j)\) と，また \(x\) 本目の橋のことを橋 \(x\) と表記します．

封鎖する橋を全探索し，それぞれの橋を封鎖した際のツアーの長さを，すべての橋に対して計算することを考えます．

まず橋 \(N\) を封鎖する際のツアーの長さを愚直に計算します．この場合は，\(dist(i, i + 1) = |X_i - X_{i+1}|\) なので，これは \(\sum_{1 \leq i \leq M - 1}|X_i - X_{i+1}|\) と計算することで，\(O(M)\) でできます．

次に，橋 \(N\) 以外を封鎖した場合のツアーの長さの計算ですが，封鎖する橋の番号を変えるとツアーの長さの計算がやや煩雑になります．この場合，封鎖する橋の番号は常に \(N\) とする代わりに，すべての島および橋の番号を同じ値だけ増やしたことにする（ただし，島 \(N+1, N+2, \dots\) は島 \(1, 2, \dots\) と考える）と，ツアーの長さの計算を行いやすくなります．

すべての島および橋の番号を \(1\) ずつ増やしながら，ツアーの長さの値を順番に計算していくことを考えます．先述の通り，封鎖している橋はすべて \(N\) であるとみなすため，ツアーの長さの計算方法は常に \(\sum_{1 \leq i \leq M - 1}|X_i - X_{i+1}|\) であり，各 \(X_i\) が変化していくことになります．

\(X_i\) の値は基本的にすべて \(1\) ずつ増えるため，\(|X_i - X_{i + 1}|\) の値は基本的には変わりません．しかし，\(X_i\) が元々 \(N\) であった場合のみ，\(X_i\) の値が \(1\) に変化するため，この場合だけは \(|X_i - X_{i+1}|\) の値が変化します．したがって，ツアーの長さの計算を行う際は，この部分のみを更新していけばよいです（※）．

問題は（※）の計算量ですが，すべての場合についてのツアーの長さの計算を行う過程で，各 \(i\) に対して，\(X_i\) の値が \(N\) から \(1\) に変化するのは，\(1\) 回のみです．したがって，（※）は全体で \(O(M)\) で実行できます．

したがって，この問題は \(O(N+M)\) で解くことができます．

実装例（C++）