40分求助QAQ
查看原帖
40分求助QAQ
386890
Kogenta楼主2021/9/2 08:28

大概思路也就是从1号节点出发,开dis数组记录到i时的总信号衰减强度为disidis_i(如果这个值超过初始强度t,则令disi=0dis_i =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;
}
2021/9/2 08:28
加载中...