3510. 【NOIP2013模拟11.5B组】最短路径(path)

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分

代码

var
  n,b1,b2:longint;
  x,y:array [0..1001] of longint;
  f,b:array [0..1001,0..1001] of real;
procedure init;
var
  i:longint;
begin
  readln(n,b1,b2);
  b1:=b1+1; b2:=b2+1;
  for i:=1 to n do
    readln(x[i],y[i]);
end;

function min(o,p:real):real;
begin
  if o<p then exit(o);
  exit(p);
end;

function max(o,p:longint):longint;
begin
  if o>p then exit(o);
  exit(p);
end;

procedure main;
var
  i,j,k:longint;
begin
  for i:=1 to n-1 do
    for j:=i+1 to n do
      begin
        b[i,j]:=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
        b[j,i]:=b[j,i];
      end;
  for i:=0 to n do
    for j:=0 to n do
      f[i,j]:=maxlongint div 3;
  f[1,1]:=0;
  for i:=1 to n do
    for j:=1 to n do
      if (i<>j) or (i=1) then
        begin
          k:=max(i,j)+1;
          if k=n+1 then
            begin
              if i<>n then f[n,n]:=min(f[n,n],f[i,j]+b[i,n]);
              if j<>n then f[n,n]:=min(f[n,n],f[i,j]+b[j,n]);
              continue;
            end;
          if k<>b1 then f[i,k]:=min(f[i,k],f[i,j]+b[j,k]);
          if k<>b2 then f[k,j]:=min(f[k,j],f[i,j]+b[i,k]);
        end;
  writeln(f[n,n]:0:2);
end;

begin
  init;
  main;
end.