【NOIP2016练习】T2 花花的聚会（树形DP，倍增）

题意：

花花住在 H 国。H 国有 n 个城市，其中 1 号城市为其首都。城市间有 n 1 条单向道路。从任意一个城市出发，都可以沿着这些单向道路一路走到首都。事实上，从任何一个城市走到首都的路径是唯一的。

过路并不是免费的。想要通过某一条道路，你必须使用一次过路券。H 国一共有 m 种过路券，每张过路券以三个整数表示：v k w：你可以在城市 v 以价格 w 买到一张过路券。这张券可以使用 k 次。这意味着，拿着这张券通过了 k 条道路之后，这张券就不能再使用了。

请注意你同一时间最多只能拥有最多一张过路券。但你可以随时撕掉手中已有的过路券，并且在所在的城市再买一张。

花花家在首都。他有 q 位朋友，他希望把这些朋友们都邀请到他家做客。所以他想要知道每位朋友要花多少路费。他的朋友们都很聪明，永远都会选择一条花费最少的方式到达首都。

花花需要准备晚餐去了，所以他没有时间亲自计算出朋友们将要花费的路费。你可以帮帮他么？

4.2 输入格式

输入的第一行包含两个空格隔开的整数 n 和 m，表示 H 国的城市数量和过路券的种数。之后的 n 1 行各自包含两个数 a_i 和 b_i，代表城市 a_i 到城市 b_i 间有一条单向道路。

之后的 m 行每行包括三个整数 v_i; k_i 和 w_i，表示一种过路券。下一行包含一个整数 q，表示花花朋友的数量。

之后的 q 行各自包含一个整数，表示花花朋友的所在城市。

4.3 输出格式

输出共 q 行，每一行代表一位朋友的路费。

对于 100% 的数据：n; m; q 10⁵; w_i 10000; 1 v_i; k_i n

思路：

 var f,g:array[..,..]of longint;

     head,vet,next,hq,vq,nq,lq,dp:array[..]of longint;

     n,m,i,tot,tq,x,q,y,v,k,w:longint;

 procedure add(a,b:longint);

 begin

  inc(tot);

  next[tot]:=head[a];

  vet[tot]:=b;

  head[a]:=tot;

 end;

 procedure adq(a,b,c:longint);

 begin

  inc(tq);

  nq[tq]:=hq[a];

  vq[tq]:=b;

  lq[tq]:=c;

  hq[a]:=tq;

 end;

 function min(x,y:longint):Longint;

 begin

  if x<y then exit(x);

  exit(y);

 end;

 function clac(x,y:longint):longint;

 var i:longint;

 begin

  clac:=;

  for i:= downto  do

   if y and (<<i)> then

   begin

    clac:=min(clac,g[x,i]);

    x:=f[x,i];

   end;

 end;

 procedure dfs(u,fa:longint);

 var e,v,i:longint;

 begin

  e:=hq[u];

  while e<> do

  begin

   dp[u]:=min(dp[u],lq[e]+clac(u,vq[e]));

   e:=nq[e];

  end;

  e:=head[u];

  while e<> do

  begin

   v:=vet[e];

   if v<>fa then

   begin

    f[v,]:=u;

    g[v,]:=dp[u];

    for i:= to  do

    begin

     f[v,i]:=f[f[v,i-],i-];

     g[v,i]:=min(g[v,i-],g[f[v,i-],i-]);

    end;

    dfs(v,u);

   end;

   e:=next[e];

  end;

 end;

 begin

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

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

  readln(n,m);

  for i:= to n- do

  begin

   readln(x,y);

   add(x,y);

   add(y,x);

  end;

  for i:= to m do

  begin

   readln(v,k,w);

   adq(v,k,w);

  end;

  for i:= to n do dp[i]:=;

  dp[]:=;

  dfs(,-);

  readln(q);

  for i:= to q do

  begin

   readln(x);

   writeln(dp[x]);

  end;

  close(input);

  close(output);

 end.

巴特西

【NOIP2016练习】T2 花花的聚会（树形DP，倍增）

最新文章

热门文章

巴特西

【NOIP2016练习】T2 花花的聚会 （树形DP，倍增）

最新文章

热门文章

【NOIP2016练习】T2 花花的聚会（树形DP，倍增）