GDOI DAY1 T3
  • 板块灌水区
  • 楼主cym_yyds
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/4/17 12:54
  • 上次更新2023/10/28 03:29:37
查看原帖
GDOI DAY1 T3
224546
cym_yyds楼主2022/4/17 12:54

请问一下两种写法有啥区别 第二种会爆栈吗

第一种

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N=1e5+10,M=1e5+10;
typedef pair<int,pair<int,int> > PIII;
int n,w[N];
int h[N],ne[M],e[M],idx=1;
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
priority_queue<PIII>q;
int res=1e9; 
int main()
{
//	freopen("line.in","r",stdin);
//	freopen("line.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>w[i];
	for(int i=2;i<=n;i++)
	{
		int fa;
		cin>>fa;
		add(fa,i);
	}
	q.push({w[1],{1,1}});
	while(!q.empty())
	{
		PIII t=q.top();
		res=min(res,t.x*t.y.y);
		q.pop();
		if(h[t.y.x]==0)break ;
		for(int i=h[t.y.x];i;i=ne[i])
		{
			int j=e[i];
			q.push({w[j],{j,t.y.y+1}});
		}
		//get(t.y.x,t.y.y);
	}
	cout<<res<<endl;
	return 0;
}

第二种

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N=1e5+10,M=1e5+10;
typedef pair<int,pair<int,int> > PIII;
int n,w[N];
int h[N],ne[M],e[M],idx=1;
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
priority_queue<PIII>q;
int res=1e9; 
void get(int u,int cnt)
{
	res=min(res,q.top().x*q.top().y.y);
	q.pop();
	if(h[u]==0)return ;
	for(int i=h[u];i;i=ne[i])
	{
		int j=e[i];
		q.push({w[j],{j,cnt+1}});
	}
	PIII t=q.top();
	get(t.y.x,t.y.y);
}
int main()
{
//	freopen("line.in","r",stdin);
//	freopen("line.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>w[i];
	for(int i=2;i<=n;i++)
	{
		int fa;
		cin>>fa;
		add(fa,i);
	}
	q.push({w[1],{1,1}});
	get(1,1);
	cout<<res<<endl;
	return 0;
}

2022/4/17 12:54
加载中...