警示后人,如果你WA 60 on #1,3,4,8
查看原帖
警示后人,如果你WA 60 on #1,3,4,8
656765
STARSczy楼主2024/4/15 16:01

你可能没有完全清空虚数。因为每次 dp 时清空必须要到达每个节点。

int dp(int x,int now){
	int ans=0;
	for(auto &[i,w]:ve[x]) if(t[i]==now) ans+=w;
	else ans+=min(w,dp(i,now));
	ve[x].clear();
	return ans;
}

应改成

int dp(int x,int now){
	int ans=0;
	for(auto &[i,w]:ve[x]){
		int tmp=dp(i,now);
		if(t[i]==now) ans+=w;
		else ans+=min(w,tmp);
	}
	ve[x].clear();
	return ans;
}
2024/4/15 16:01
加载中...