题目描述
数据范围
解法
由于同一个点，同一个圆盘最多只会走一次。
把(i,j)当作一个点，表示第i个点，放第i个圆盘。
那么就可以使用最短路。
时间复杂度为
事实上存在冗余圆盘，一个相对某个圆盘又贵又小的圆盘即是冗余圆盘。
给圆盘排序，那么令(i,j)只给(k,l)连一条边使得l最小，(i,j)给(i,j+1)连一条边。
那么任意一条原图中的边就可以分解为上述两类边。
那么边数就降到
spfa的时间复杂度为
如果使用dijstra的时间复杂度为
代码
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.启发
去除冗余
差分
本题中：原图共有
并且
那么(x,z)这条边显然可以省略。
当大量存在这样的边时，如本题，就可以优化边数。
spfa优化
1.SFL优化
尽量维持决策遍历队列的单调性，这样可以使得以更高的频率用更优的点更新。
具体而言，如果dis[b[head+1]]>dis[b[tail]]，则swap(b[head+1],b[tail])。
2.单点最短路优化
由于spfa自带求单源到所有点的最短路，如果我们只需要求单源到单汇的最短路，那么显然如果当前节点比目标节点更劣就直接跳过。