vector<int>tree[MAXN+1]和int e[N],h[N],ne[N],idx?

Question

Park Visit

 HDU - 4607

这两个用vector就ac了 e[N]TLE了  所以我想知道这两种在点数和边数在什么情况下时间或空间最有力 .?谢谢

#include<stdio.h>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;

const int N=1e5+10;

vector<int>G[N];

int e[N],h[N],ne[N],idx;
int dis[N];

void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u)
{
	for(int i=0;i<G[u].size();i++)
	{
		int j=G[u][i];
		if(!dis[j])
		{
			dis[j]=dis[u]+1;
			dfs(j);
		}	
	}
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		//memset(h,-1,sizeof h);idx=0;
		int n,m;
		
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)G[i].clear();
		for(int i=0;i<n-1;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			G[u].push_back(v);
			G[v].push_back(u);
		}
		
		memset(dis,0,sizeof dis);
		dis[1]=1;dfs(1);
		int st=1;
		for(int i=2;i<=n;i++)
			if(dis[i]>dis[st])st=i;
			
		memset(dis,0,sizeof dis);		
		dis[st]=1;dfs(st);
		int end=1;
		for(int i=2;i<=n;i++)
			if(dis[i]>dis[end])end=i;
        
        int ma=dis[end];
        
		for(int i=0;i<m;i++)
		{
			int k;
			scanf("%d",&k);

			if(ma<k) printf("%d\n",ma-1-(ma-k)*2);
			else printf("%d\n",k-1);
		}

	}
}

#include<stdio.h>
#include<cstring>
#include<iostream>
using namespace std;

const int N=1e5+10;

int e[N],h[N],ne[N],idx;
int dis[N];

void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u)
{
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(!dis[j])
		{
			dis[j]=dis[u]+1;
			dfs(j);
		}	
	}
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		memset(h,-1,sizeof h);idx=0;
		int n,m;
		
		scanf("%d%d",&n,&m);
		for(int i=0;i<n-1;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			add(u,v);
			add(v,u);
		}
		
		memset(dis,0,sizeof dis);
		dis[1]=1;dfs(1);
		int st=1;
		for(int i=2;i<=n;i++)
			if(dis[i]>dis[st])st=i;
			
		memset(dis,0,sizeof dis);		
		dis[st]=1;dfs(st);
		int end=1;
		for(int i=2;i<=n;i++)
			if(dis[i]>dis[end])end=i;
        
        int ma=dis[end];
        
		for(int i=0;i<m;i++)
		{
			int k;
			scanf("%d",&k);

			if(ma<k) printf("%d\n",ma-1-(ma-k)*2);
			else printf("%d\n",k-1);
		}

	}
}

Answer 1

你这是典型的迪杰斯特拉(Dijkstra)算法问题，可以加深对这个算法的理解再来刷题