路径规划

• 独立做出了百度之星决赛的金牌题，开心~
• 动态转移的时候直接新开一个数组存储历史值，更清晰简洁，不给自己找麻烦
• 在memcpy语句中，被操纵的数组在前

点击查看代码

#include <bits/stdc++.h>
using namespace std;
vector<int>a[100005],c[100005];
int cnt[100005];
long long f[100005][105][2],g[105][2],len[100005];
int w[105];
int n,m;
void dp(int n1,int fa)
{if(a[n1].size()==1&&n1!=1){cnt[n1]=1;}f[n1][0][0]=f[n1][0][1]=0;for(int i=0;i<a[n1].size();i++){if(a[n1][i]!=fa){int k=a[n1][i];dp(k,n1);cnt[n1]+=cnt[a[n1][i]];memcpy(g,f[n1],sizeof(f[n1]));len[n1]=max(len[n1],len[a[n1][i]]+c[n1][i]);f[n1][0][1]=f[n1][0][1]+f[a[n1][i]][0][1]+2*c[n1][i];f[n1][0][0]=f[n1][0][1]-len[n1];for(int j=1;j<min(cnt[n1],m+1);j++){f[n1][j][0]=min(g[j][1]+f[k][0][0]+c[n1][i],g[j][0]+f[k][0][1]+2*c[n1][i]);f[n1][j][0]=min(f[n1][j][0],g[j-1][0]+f[k][0][0]+c[n1][i]);for(int l=1;l<=cnt[k];l++){if(j-l<0){break;}if(l<cnt[k]){f[n1][j][0]=min(f[n1][j][0],g[j-l][1]+f[k][l][0]+c[n1][i]);}f[n1][j][0]=min(f[n1][j][0],g[j-l][0]+f[k][l][1]+2*c[n1][i]);}}for(int j=1;j<=min(cnt[n1],m);j++){f[n1][j][1]=g[j][1]+f[k][0][1]+2*c[n1][i];f[n1][j][1]=min(f[n1][j][1],g[j-1][0]+f[k][0][0]+c[n1][i]);for(int l=1;l<=cnt[k];l++){if(j-l<0){break;}f[n1][j][1]=min(f[n1][j][1],g[j-l][1]+f[k][l][1]+2*c[n1][i]);if(j-l-1>=0){f[n1][j][1]=min(f[n1][j][1],g[j-l-1][0]+f[k][l][0]+c[n1][i]);}}}}}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);memset(f,0x3f,sizeof(f));cin>>n>>m;for(int i=1;i<n;i++){int u,v,w;cin>>u>>v>>w;a[u].push_back(v);a[v].push_back(u);c[u].push_back(w);c[v].push_back(w);}for(int i=1;i<=m;i++){cin>>w[i];}dp(1,0);sort(w+1,w+m+1);int cur=0;long long ans=INT_MAX;for(int i=0;i<=min(m,cnt[1]);i++){ans=min(ans,f[1][i][1]+cur);cur+=w[i+1];}cout<<ans<<endl;return 0;
}