过了但疑惑
查看原帖
过了但疑惑
642144
This_Rrhar楼主2024/3/27 17:07

这是 AC 代码的片段:

void calc(ll u)
{
	dp[cur=0]=0,d[u]=0;
	for(pii i:e[u])if(!vis[i.first])
	{
		ll st=cur+1;
		getDis(i.first,u,i.second,1);
		for(int j=st;j<=cur;j++)ans=min(ans,dp[k-d[a[j]]]+dep[a[j]]);
		for(int j=st;j<=cur;j++)dp[d[a[j]]]=min(dp[d[a[j]]],dep[a[j]]);
	}
	for(int i=1;i<=cur;i++)dp[d[a[i]]]=1e9;
}

但是将这两句对调会挂 25pts:

for(int j=st;j<=cur;j++)ans=min(ans,dp[k-d[a[j]]]+dep[a[j]]);
for(int j=st;j<=cur;j++)dp[d[a[j]]]=min(dp[d[a[j]]],dep[a[j]]);

不应该先 dp 后更新 ans 吗?

2024/3/27 17:07
加载中...