题目描述

数据范围

解法

由于同一个点，同一个圆盘最多只会走一次。

把(i,j)当作一个点，表示第i个点，放第i个圆盘。

那么就可以使用最短路。

时间复杂度为O(n4∗k)。

事实上存在冗余圆盘，一个相对某个圆盘又贵又小的圆盘即是冗余圆盘。

给圆盘排序，那么令(i,j)只给(k,l)连一条边使得l最小，(i,j)给(i,j+1)连一条边。

那么任意一条原图中的边就可以分解为上述两类边。

那么边数就降到n3。

spfa的时间复杂度为O(n3∗k)。

如果使用dijstra的时间复杂度为O(n3∗logn)。

代码

Const

        maxn=257;

Type

        longint=cardinal;

Var

        t,n,m,w,i,j,k,l:cardinal;

        dis:array[1..maxn,1..maxn] of longint;

        bz:array[1..maxn,1..maxn] of boolean;

        a:array[1..maxn,0..1] of longint;

        b:array[0..maxn,0..1] of longint;

        c:array[0..maxn*maxn*maxn,0..1] of word;

        ban:array[1..maxn] of boolean;

        d:array[0..maxn] of longint;

        head,tail:longint;

        ans:longint;

        path:array[1..maxn,1..maxn,1..maxn] of word;

        fi:array[1..maxn,1..maxn] of longint;

        la:array[1..maxn*maxn*maxn] of longint;

        ne:array[1..maxn*maxn*maxn] of longint;

        cnt,tot:longint;

        x,y,z:longint;

Function min(a,b:longint):longint;

begin

        if (a>b) then exit(b);

        exit(a);

end;

Procedure add_line(a,b,c:longint);

begin

        inc(tot);

        ne[tot]:=fi[a][b];

        la[tot]:=c;

        fi[a][b]:=tot;

end;

Procedure add(x,y,z:longint);

begin

        if (dis[x][y]>z) then

        begin

                dis[x][y]:=z;

                if (z<ans) and (bz[x][y]=false) then

                begin

                        inc(tail);

                        c[tail][0]:=x;

                        c[tail][1]:=y;

                        bz[x][y]:=true;

                        if (head<tail) and (dis[c[head+1][0]][c[head+1][1]]>dis[c[tail][0]][c[tail][1]]) then

                        begin

                                c[0]:=c[tail];

                                c[tail]:=c[head+1];

                                c[head+1]:=c[0];

                        end;

                end;

        end;

end;

Procedure qsort(l,r:longint);

var

        i,j,k,mid,mm,tmp:longint;

begin

        i:=l;

        j:=r;

        mid:=b[(l+r) div 2][0];

        repeat

                while (b[i][0]<mid) do inc(i);

                while (b[j][0]>mid) do dec(j);

                if (i<=j) then

                begin

                        b[0]:=b[i];

                        b[i]:=b[j];

                        b[j]:=b[0];

                        dec(j);

                        inc(i);

                end;

        until i>j;

        if (i<r) then qsort(i,r);

        if (l<j) then qsort(l,j);

end;

Function judge(i,j,k,l:longint):boolean;

begin

        exit(int64(a[i][0]-a[j][0])*(a[i][0]-a[j][0])+(a[i][1]-a[j][1])*(a[i][1]-a[j][1])<=int64(b[l][0]+b[k][0])*(b[l][0]+b[k][0]));

end;

Procedure extreme;

begin

        qsort(1,m);

        for i:=1 to n do

                for j:=1 to n do

                begin

                        l:=1;

                        for k:=m downto 1 do

                        begin

                                while (l<=m) do

                                begin

                                        if (judge(i,j,k,l)) then

                                        begin

                                                path[i][k][j]:=l;

                                                break;

                                        end

                                        else inc(l);

                                end;

                                if (path[i][k][j]>0) then add_Line(i,k,j);

                        end;

                end;

end;

Procedure spfa;

var

        i,j,k:cardinal;

Begin

        while (head<tail) do

        begin

                inc(head);

                if (c[head][1]<m) then

                begin

                        add(c[head][0],c[head][1]+1,dis[c[head][0]][c[head][1]]+b[c[head][1]+1][1]-b[c[head][1]][1]);

                end;

                k:=fi[c[head][0]][c[head][1]];

                while (k>0) do

                begin

                        i:=la[k];

                        j:=path[c[head][0]][c[head][1]][i];

                        add(i,j,dis[c[head][0]][c[head][1]]+b[j][1]);

                        k:=ne[k];

                end;

                if (a[c[head][0]][1]+b[c[head][1]][0]>=w) then ans:=min(dis[c[head][0]][c[head][1]],ans);

                bz[c[head][0]][c[head][1]]:=false;

        end;

End;

Procedure prepare;

begin

        readlN(n,m,w);

        for i:=1 to n do

        begin

                readln(a[i][0],a[i][1]);

        end;

        for i:=1 to m do

        begin

                readln(b[i][0],b[i][1]);

        end;

        fillchar(ban,sizeof(ban),0);

        for i:=1 to m do for j:=i+1 to m do

                if (b[i][0]>=b[j][0]) and (b[i][1]<=b[j][1]) then ban[j]:=true

                else if (b[i][0]<=b[j][0]) and (b[i][1]>=b[j][1]) then ban[i]:=true;

        d[0]:=0;

        for i:=1 to m do if (ban[i]=false) then

        begin

                inc(d[0]);

                d[d[0]]:=i;

        end;

        for i:=1 to d[0] do b[i]:=b[d[i]];

        m:=d[0];

        fillchar(dis,sizeof(dis),127);

        fillchar(path,sizeof(path),0);

        fillchar(fi,sizeof(fi),0);

        tot:=0;

        head:=0;

        tail:=0;

        ans:=maxlongint;

        extreme;

        for i:=1 to n do

                for j:=1 to m do

                begin

                        if (b[j][0]>=a[i][1]) then

                        begin

                                add(i,j,b[j][1]);

                                break;

                        end;

                end;

end;

Procedure getans;

begin

        if (ans<2000000000) then writeln(ans)

        else writeln('impossible');

end;

Begin

        assign(input,'river.in');reset(input);

        assign(output,'river.out');rewrite(output);

        readln(t);

        for t:=1 to t do

        begin

                prepare;

                spfa;

                getans;

        end;

        //writeln(cnt);

        close(output);close(input);

End.

启发

去除冗余

差分

本题中：原图共有n4，考虑到如果(i,j)可以到达(k,l)，那么(i,j)也一定可以到达(k,l’)，其中l’的半径比l大。如果存在这样的关系：



并且dis[x][z]=dis[y][z]+dis[x][y]。

那么(x,z)这条边显然可以省略。

当大量存在这样的边时，如本题，就可以优化边数。

spfa优化

1.SFL优化

尽量维持决策遍历队列的单调性，这样可以使得以更高的频率用更优的点更新。

具体而言，如果dis[b[head+1]]>dis[b[tail]]，则swap(b[head+1],b[tail])。

2.单点最短路优化

由于spfa自带求单源到所有点的最短路，如果我们只需要求单源到单汇的最短路，那么显然如果当前节点比目标节点更劣就直接跳过。