记录编号	418536	评测结果	AAAWWWWAW
题目名称	信号放大器	最终得分	44
用户昵称	h	是否通过	未通过
代码语言	C++	运行时间	0.019 s
提交时间	2017-06-30 18:46:18	内存使用	3.72 MiB

#include<cstdio>
#include<algorithm>
#define R register
#define N 100007

struct info{
  int pre,to,dis;
}edge[2*N];

int n,size,ans,signal,head[N],f[N],fa[N];

void addline(int from,int to,int dis){
  edge[++size].pre=head[from];head[from]=size;
  edge[size].to=to;edge[size].dis=dis;
}

void tsdp(int k){
  f[k]=1;
  for (R int i=head[k];i;i=edge[i].pre)
  if (fa[k]!=edge[i].to){
	fa[edge[i].to]=k;
	tsdp(edge[i].to);
	int t=f[edge[i].to]+edge[i].dis;
	if (t<=signal) f[k]=std::max(f[k],t);
	else ++ans,f[k]=std::max(f[k],1+edge[i].dis);
  }
}

int main(){
  freopen("booster.in","r",stdin);
  freopen("booster.out","w",stdout);
  scanf("%d",&n);
  for (R int i=1;i<=n;++i){
    int k;scanf("%d",&k);
    for (R int j=1;j<=k;++j){
	  int to,dis;
	  scanf("%d%d",&to,&dis);
	  addline(i,to,dis);
    }
  }
  scanf("%d",&signal);
  for (R int i=1;i<=size;++i)
  if (edge[i].dis>=signal){
	printf("No solution.");
	return 0;
  }
  tsdp(1);
  printf("%d",ans);
  return 0;
}