Description
平面内給出 n 個點，記橫坐标最小的點為 A，最大的點為 B，現在Zxd想要知道在每個點經過一次（A 點兩次）的情況下從 A 走到 B，再回到 A 的最短路徑。但他是個強迫症患者，他有許多奇奇怪怪的要求與限制條件：
1. 從 A 走到 B 時，隻能由橫坐标小的點走到大的點。
2. 由 B 回到 A 時，隻能由橫坐标大的點走到小的點。
3. 有兩個特殊點 b1 和 b2， b1 在 0 到 n-1 的路上，b2 在 n-1 到 0 的路上。
請你幫他解決這個問題助他治療吧！
Input
第一行三個整數 n,b1,b2,( 0 < b1，b2 < n-1 且 b1 <> b2)。n 表示點數，從 0 到 n-1 編号，b1 和 b2 為兩個特殊點的編号。
以下 n 行，每行兩個整數 x、y 表示該點的坐标(0 <= x，y <= 2000)，從 0 号點順序
給出。Doctor Gao為了友善他的治療，保證所有點橫坐标不同，并且已經将給出的點按 x 增序排好了。
Output
僅一行，輸出最短路徑長度（精确到小數點後面 2 位）
Solutions
考慮到每個點隻能走一次，且從終點往回走和從起點再走一遍到終點沒有差別，是以這道題可以轉化為求兩條不相交路徑和的最小值。
于是考慮用動态規劃求解。
用F[i][j]表示第一個點走到i,第二個點(回去的那個點)走到j的最優值。
為了保證更新時不會更新出F[i][i](即一個點走了兩次)，而且每個點都會在路徑上，我們每次用F[i][j]去更新點max(i,j)+1，是以轉移方程為：
F[0][0]=0; k=max(i,j)+1，
F[k][j]=max(F[k][j],F[i][j]+Dis(i,k));
F[i][k]=max(F[i][k],F[i][j]+Dis(j,k));
Dis(i,j)為從i直接走到j點的距離.
對于兩個特殊點和max(i,j)=N的情況特判處理即可。
期望得分：100（本代碼為此做法）
同時上面的DP也可以用記憶化搜尋實作，對于abs(x-y)>1的情況，說明目前情況隻能從max(x,y)-1轉移過來，當abs(x-y)=1時，則能從1~min(x,y)中的任意一點轉移過來，于是用記憶化搜尋完成上面的步驟，加上适當剪枝即可。
期望得分：60~100分
代碼
1 var
2 n,b1,b2:longint;
3 x,y:array [0..1001] of longint;
4 f,b:array [0..1001,0..1001] of real;
5 procedure init;
6 var
7 i:longint;
8 begin
9 readln(n,b1,b2);
10 b1:=b1+1; b2:=b2+1;
11 for i:=1 to n do
12 readln(x[i],y[i]);
13 end;
14
15 function min(o,p:real):real;
16 begin
17 if o<p then exit(o);
18 exit(p);
19 end;
20
21 function max(o,p:longint):longint;
22 begin
23 if o>p then exit(o);
24 exit(p);
25 end;
26
27 procedure main;
28 var
29 i,j,k:longint;
30 begin
31 for i:=1 to n-1 do
32 for j:=i+1 to n do
33 begin
34 b[i,j]:=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
35 b[j,i]:=b[j,i];
36 end;
37 for i:=0 to n do
38 for j:=0 to n do
39 f[i,j]:=maxlongint div 3;
40 f[1,1]:=0;
41 for i:=1 to n do
42 for j:=1 to n do
43 if (i<>j) or (i=1) then
44 begin
45 k:=max(i,j)+1;
46 if k=n+1 then
47 begin
48 if i<>n then f[n,n]:=min(f[n,n],f[i,j]+b[i,n]);
49 if j<>n then f[n,n]:=min(f[n,n],f[i,j]+b[j,n]);
50 continue;
51 end;
52 if k<>b1 then f[i,k]:=min(f[i,k],f[i,j]+b[j,k]);
53 if k<>b2 then f[k,j]:=min(f[k,j],f[i,j]+b[i,k]);
54 end;
55 writeln(f[n,n]:0:2);
56 end;
57
58 begin
59 init;
60 main;
61 end.