大概思路也就是从1号节点出发,开dis数组记录到i时的总信号衰减强度为disi(如果这个值超过初始强度t,则令disi=0,再继续往下搜,就是不知道为什么只有40分哇QAQ,大神帮看看吧,球球了
贴份代码:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=20050;
vector<int>v[maxn],val[maxn];
int ans;
bool p[maxn];
int t;
int dis[maxn];
void dfs(int x){
p[x]=1;
for(int i=0;i<v[x].size();i++){
if(!p[v[x][i]]){
dis[v[x][i]]=dis[x]+val[x][i];
if(dis[v[x][i]]>=t){
dis[v[x][i]]=0;
ans++;
}
dfs(v[x][i]);
}
}
}
int main(){
int n;
cin>>n;
int m,x,y;
int maxrec=0;
for(int i=1;i<=n;i++){
cin>>m;
for(int j=1;j<=m;j++){
cin>>x>>y;
v[i].push_back(x);
val[i].push_back(y);
maxrec=max(maxrec,y);
}
}
cin>>t;
if(maxrec>=t){
cout<<"No solution."<<endl;
return 0;
}
ans=0;
dfs(1);
cout<<ans<<endl;
return 0;
}