求如下代码的时间复杂度
  • 板块灌水区
  • 楼主qzilr
  • 当前回复18
  • 已保存回复18
  • 发布时间2022/8/16 19:34
  • 上次更新2023/10/27 15:06:00
查看原帖
求如下代码的时间复杂度
400333
qzilr楼主2022/8/16 19:34

RT

#include<bits/stdc++.h>
#define fir first
#define sec second
using namespace std;
const int N=1e6+6;
const long long INF=1e12;
struct node{
	int v,w,nxt;
}g[N*2];
int h[N],tot=0,cnt;
int n,k,p,s,t,mx;
void add(int u,int v,int w){
	g[++tot]=(node){v,w,h[u]};
	h[u]=tot;
}
int depth[N],use[N];
void dfs(int u,int fa){
	depth[u]=depth[fa]+1;
	mx=max(mx,depth[u]);
	for(int i=h[u];~i;i=g[i].nxt){
		if(!use[g[i].v])
			use[g[i].v]=1,dfs(g[i].v,u);
	}
}
long long d[N];
typedef pair<long long,int> P;
priority_queue<P,vector<P>,greater<P> >q;
int vis[N];
void dij(int s){
	q.push(P(0,s));d[s]=0;
	while(!q.empty()){
		int u=q.top().sec;q.pop();
		if(vis[u])	continue;
		vis[u]=1;
		for(int i=h[u];~i;i=g[i].nxt){
			int v=g[i].v;
			if(d[v]>d[u]+g[i].w){
				d[v]=d[u]+g[i].w;
				if(!vis[v])	q.push(P(d[v],v));
			}
		}
	}
}
int main(){
	freopen("T1.in","r",stdin);
	int T;scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=N;i++)	h[i]=-1,d[i]=INF,vis[i]=0,use[i]=0;
		tot=0;mx=0;depth[0]=0;use[0]=1;use[1]=1;
		for(int i=1;i<n;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			add(u,v,w),add(v,u,w);
		}
		scanf("%d%d%d%d",&k,&p,&s,&t);
		dfs(1,0);
		for(int i=1;i<=n;i++){
			add(i,n+depth[i],0);
			if(depth[i]>k)	add(n+depth[i]-k,i,p);
			if(depth[i]+k<=mx)	add(n+depth[i]+k,i,p);
		}
		dij(s);
		printf("%lld\n",d[t]);
	}
	return 0;
}
2022/8/16 19:34
加载中...