この問題は、都市２から都市 \(N\) までのすべての順列を全探索し、その中の最小距離を出力するとACとなります。
入力例１だと、(1,2,3,4), (1,2,4,3), (1,3,2,4), (1,3,4,2), (1,4,2,3), (1,4,3,2)がすべての順列となっています。
順列の全探索は普通に実装するのは難しいですが、pythonでは、itertoolsのpermutationsを使うと簡単に順列を順番に取り出せます。
具体的には、それぞれの順列で、\(1 ≤ i ≤ N-1\) に関して、都市 \(i\) と都市 \(i+1\) の距離を加算します。最後に都市 \(N\) と都市１の距離を加算します。
距離は、\[\sqrt{(A_i-A_{i+1})^2+(B_i-B_{i+1})^2}\] で計算できます。
実装例