dij40pts求助(玄关)
查看原帖
dij40pts求助(玄关)
1287433
__ycy1124__楼主2024/9/25 15:25
#include<bits/stdc++.h>
#define hy for(int i=1;i<=n;i++){bj[i]=0;}
#define int long long
using namespace std;
struct Node{
	int to,w;
};
vector <Node> a[1001];
int js[1001][2];
struct qaq{
	int w,p;
}b[2001];
int tot=0;
bool bj[1001];
void work(int x){
	if(x*2+1<=tot&&b[x*2].w<b[x*2+1].w&&b[x*2].w>b[x*2+1].w){
		swap(b[x],b[x*2+1]);
		work(x*2+1);
	}
	else if(x*2<=tot&&b[x*2].w<b[x].w){
		swap(b[x*2],b[x]);
		work(x*2);
	}
}
void work1(int x){
	if(b[x].w<b[x/2].w&&x!=1){
		swap(b[x],b[x/2]);
		work1(x/2);
	}
}
void dij(int p,int w,int qwq){
	bj[p]=1;
	js[p][qwq]=w;
	for(auto it:a[p]){
		if(!bj[it.to]){
			b[++tot]={w+it.w,it.to};
			work1(tot);
		}
	}
}
signed main(){
	int n;
	scanf("%lld",&n);
	for(int i=1;i<n;i++){
		int w,u;
		scanf("%d%lld",&u,&w);
		a[i+1].push_back({u,w});
		a[u].push_back({i+1,w});
	}
	b[++tot]={0,1};
	while(tot){
		dij(b[1].p,b[1].w,0);
		swap(b[1],b[tot]);
		tot--;
		work(1);
	}
	hy
	int s=0;
	for(int i=1;i<=n;i++){
		if(js[i][0]>js[s][0]){
			s=i;
		}
	}
	b[++tot]={0,s};
	while(tot){
		dij(b[1].p,b[1].w,0);
		swap(b[1],b[tot]);
		tot--;
		work(1);
	}
	hy
	int t=0;
	for(int i=1;i<=n;i++){
		if(js[i][0]>js[t][0]){
			t=i;
		}
	}
	b[++tot]={0,t};
	while(tot){
		dij(b[1].p,b[1].w,1);
		swap(b[1],b[tot]);
		tot--;
		work(1);
	}
//	printf("%d %d\n",s,t);
	for(int i=1;i<=n;i++){
		printf("%lld\n",max(js[i][0],js[i][1]));
	}
	return 0;
}
2024/9/25 15:25
加载中...