bzoj2763

扫码查看

首先是稀疏图,不难想到dij+heap

观察题目可以知道,0<=k<=10;

所以比较裸的想法就是,d[i,j]表示已经免费了i条线路后到达j的最短路

容易得到

d[i,j]:=min(d[i,j],d[i-1,k]);

d[i,j]:=min(d[i,j],d[i,k]+w[k,j]);

然后在做dij在选择中间点的时候,我们穷举一下免费的线路数就可以了;

然后就要维护10个堆……

语言表述有点渣,具体还是看程序吧

 const inf=;
type point=record
       num,dis:longint;
     end;
     node=record
       next,cost,point:longint;
     end; var edge:array[..] of node;
    heap:array[..,..] of point;
    d,where:array[..,..] of longint;
    h:array[..] of longint;
    p:array[..] of longint;
    len,x,y,z,i,j,n,m,u,k,s,t:longint; procedure swap(var a,b:point);
  var c:point;
  begin
    c:=a;
    a:=b;
    b:=c;
  end; function min(a,b:longint):longint;
  begin
    if a>b then exit(b) else exit(a);
  end; procedure add(x,y,z:longint);
  begin
    inc(len);
    edge[len].point:=y;
    edge[len].cost:=z;
    edge[len].next:=p[x];
    p[x]:=len;
  end; procedure sift(p,i:longint);
  var j,x,y:longint;
  begin
    j:=i shl ;
    while j<=h[p] do
    begin
      if (j+<=h[p]) and (heap[p,j].dis>heap[p,j+].dis) then inc(j);
      if heap[p,i].dis>heap[p,j].dis then
      begin
        x:=heap[p,i].num;
        y:=heap[p,j].num;
        where[p,x]:=j;
        where[p,y]:=i;
        swap(heap[p,i],heap[p,j]);
        i:=j;
        j:=i shl ;
      end
      else break;
    end;
  end; procedure up(p,i:longint);
  var j,x,y:longint;
  begin
    j:=i shr ;
    while j> do
    begin
      if heap[p,i].dis<heap[p,j].dis then
      begin
        x:=heap[p,i].num;
        y:=heap[p,j].num;
        where[p,x]:=j;
        where[p,y]:=i;
        swap(heap[p,i],heap[p,j]);
        i:=j;
        j:=j shr ;
      end
      else break;
    end;
  end; begin
  len:=-;
  fillchar(p,sizeof(p),);
  readln(n,m,k);
  readln(s,t);
  inc(s);  //点序号都+,习惯一点
  inc(t);
  for i:= to m do
  begin
    readln(x,y,z);
    inc(x);
    inc(y);
    add(x,y,z);
    add(y,x,z);
  end;
  for i:= to n do
    if i<>s then
    begin
      for j:= to k do
        d[j,i]:=inf;
    end
    else
      for j:= to k do
        d[j,i]:=;
  for i:= to k do
  begin
    for j:= to n do
    begin
      heap[i,j].num:=j;
      heap[i,j].dis:=d[i,j];
      where[i,j]:=j;
    end;
    h[i]:=n;
  end;
  for i:= to k do
    up(i,s);  //起点不一定是0,要初始化堆,一开始这里被坑翻了
  for u:= to n do
  begin
    for j:=k downto do 
    begin
      x:=heap[j,].num;
      y:=heap[j,h[j]].num;  
      if (h[j]=) or (d[j,x]=inf) then continue;
      where[j,y]:=;  //dij+heap比较重要的细节
      swap(heap[j,],heap[j,h[j]]);
      dec(h[j]); 
      sift(j,);  //出堆,调整堆
      i:=p[x];
      while i<>- do
      begin
        y:=edge[i].point;
        if (j<>k) and (d[j+,y]>d[j,x]) then   //两种情况
        begin
          d[j+,y]:=d[j,x];
          heap[j+,where[j+,y]].dis:=d[j+,y];
          up(j+,where[j+,y]);
        end;
        if (d[j,y]>d[j,x]+edge[i].cost) then
        begin
          d[j,y]:=d[j,x]+edge[i].cost;
          heap[j,where[j,y]].dis:=d[j,y];
          up(j,where[j,y]);
        end;
        i:=edge[i].next;
      end;
    end;
  end;
  writeln(d[k,t]); //肯定尽可能免费好啊
end.
05-11 09:39
查看更多