这是 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 吗?