思路：这个没思路，看了陈启峰的论文写得。
#include<map> #include<set> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<string> #include<iomanip> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define pb push_back #define mp make_pair #define Maxn 1010 #define Maxm 80002 #define LL __int64 #define Abs(x) ((x)>0?(x):(-(x))) #define lson(x) (x<<1) #define rson(x) (x<<1|1) #define clr(x,y) memset(x,y,sizeof(x)) #define inf 0x3f3f3f3f #define lowbit(x) (x&(-x)) #define mod 1000000000 using namespace std; int dp[Maxn][Maxn],best[Maxn],w[Maxn],d[Maxn],n,dis[Maxn],head[Maxn],vi[Maxn],e; struct Edge{ int u,v,next,val; }edge[Maxn*2]; void init() { clr(vi,0); clr(head,-1); e=0; } void add(int u,int v,int val) { edge[e].u=u,edge[e].v=v,edge[e].val=val,edge[e].next=head[u],head[u]=e++; edge[e].u=v,edge[e].v=u,edge[e].val=val,edge[e].next=head[v],head[v]=e++; } void getdis(int u,int f) { int i,v,sz; vi[u]=1; for(i=head[u];i!=-1;i=edge[i].next){ v=edge[i].v; if(v==f) continue; dis[v]=dis[u]+edge[i].val; getdis(v,u); } } void dfs(int u,int f) { int i,v,j; for(i=head[u];i!=-1;i=edge[i].next){ v=edge[i].v; if(v==f) continue; dfs(v,u); } memset(dis,0,sizeof(dis)); getdis(u,u); best[u]=inf; for(i=1;i<=n;i++){ if(dis[i]>d[u]){dp[u][i]=inf;continue;} dp[u][i]=w[i]; for(j=head[u];j!=-1;j=edge[j].next){ v=edge[j].v; if(v==f) continue; dp[u][i]+=min(best[v],dp[v][i]-w[i]); } if(dp[u][i]<best[u]) best[u]=dp[u][i]; } } int main() { int t,i,j,u,v,val; scanf("%d",&t); while(t--){ init(); scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",w+i); for(i=1;i<=n;i++) scanf("%d",d+i); for(i=1;i<n;i++){ scanf("%d%d%d",&u,&v,&val); add(u,v,val); } dfs(1,0); printf("%d ",best[1]); } return 0; }