bzoj1706: [Usaco2007 Nov]relays 奶牛接力跑 (Floyd+新姿势)

题目大意：有t(t<=100)条无向边连接两点，求s到e刚好经过n(n<=10^7)条路径的最小距离。

第一反应分层图，但是一看n就懵逼了，不会写。看了题解之后才知道可以这么玩。。。

首先有100条边最多200个点，但点编号到1000，所以离散化一下。

先把n转成2进制，按位考虑。dist[i][j][k]表示刚好经过2^i条边从j到k的最短距离，则dist[i,j,k]=min{dist[i-1][j][l]+dist[i-1][l][k]}。用类似快速幂的方法，若是2进制的n这一位是1的话，就把答案数组g和dist跑floyd(min{g[i-1][j][l]+dist[i-1][l][k]})，否则dist自己和自己跑(min{dist[i-1][j][l]+dist[i-1][l][k]})，这样子g就是跑n条路径得出的最小距离了。

代码如下：

type

  map=array[..,..]of longint;

var

  n,t,s,e,i,j,k,len,x,y,tot:longint;

  c,d,g:array[..,..]of longint;

  num:array[..]of longint;

procedure merge(var a,b:map);

var

  i,j,k:longint;

begin

  fillchar(c,sizeof(c),);

  for k:= to tot do

  for i:= to tot do

  for j:= to tot do

  if c[i,j]>a[i,k]+b[k,j] then

  c[i,j]:=a[i,k]+b[k,j];

  a:=c;

end;

procedure work;

begin

  fillchar(g,sizeof(g),);

  for i:= to tot do g[i,i]:=;

  while n> do

  begin

    if n and = then merge(g,d);

    merge(d,d);

    n:=n>>;

  end;

  writeln(g[num[s],num[e]]);

end;

begin

  readln(n,t,s,e);

  fillchar(d,sizeof(d),);

  for i:= to t do

  begin

    readln(len,x,y);

    if num[x]= then

    begin

      inc(tot);num[x]:=tot;

    end;

    if num[y]= then

    begin

      inc(tot);num[y]:=tot;

    end;

    d[num[x],num[y]]:=len;d[num[y],num[x]]:=len;

  end;

  work;

end.

巴特西

bzoj1706: [Usaco2007 Nov]relays 奶牛接力跑 (Floyd+新姿势)

最新文章

热门文章