解题思路：
这题是让你构造一个最廉价的包含所有节点的圣诞树（那就是选择“更好的边”，去除“不好的边”），看到这题的所求：就是每个边的造价是它的价格*它的所有子孙节点的权值和。这一点直接让我陷入思维死区：怎么知道谁是它的子孙节点啊，题中也没给什么说明？让我无从下手……若我就对样例中的图，去推导一下，也许会发现：一棵圣诞树的代价=各个边的价格*它的所有子孙节点的权值和=各个节点（2-n）到根节点的距离（路径上价格和）*该节点的权值 ——的和。那么要求最小的代价就是求各个点的最短路*权值的和。
感悟：
当确定没错却WA时，考虑下精度问题。刚开始按照题意的思路去思考时，却没有任何思路时；有两种选择：①试着看看按照题意能不能推出什么。②实在是推也推不出来时，一定要试着换个思路。
PS:期间WA了n次各种错误，各种坑爹，坑的人崩溃！需要注意：1.精度问题需用long long 或 __int64 2.没答案输出“No Answer”，当n为0或1是答案为0，注意敲代码时的陷阱，当结果为0时，不能表示“No Answer” 3.用Dijsktra过不了，需要用SPFA 4.最大值的取值取的小了，可能最短距离大于最大值导致错误，若取得大了，可能会导致相加溢出！这要看情况了，如果用的是邻接表的话应该把最大值取到64位的最大，因为dist[v]+data[j]不会溢出，data[j]是一个真正的值。而若用二维数组的话dist[v]+map[v][u]就会溢出了因为map[v][u]可能是最大值，不过可以判断一下即可。总之，这题出的不错哦~
View Code
///SPFA 经过各种错误蹂躏终于对了！ #include <stdio.h> #include <memory.h> #define N 50002 #define M 100002 #define MOV(x) (x=(x+1)%N) #define MAXVAL 0x7fffffffffffffff///64位最大值 int nodevp[N],nodeu[M],data[M],next[M],ind; int weight[N]; long long dist[N]; int queue[N],font,rear,inqueue[N]; long long SPFA(int s,int n) { int i,v,u; for(i=1;i<=n;i++) dist[i]=MAXVAL,inqueue[i]=0; dist[s]=0; inqueue[s]=1; font=rear=0; queue[MOV(rear)]=s; while(font!=rear) { /// 错误： /// v=queue[MOV(font)]; 找来找去，还是SPFA写错了！这里少写了inqueue[v]=0 v=queue[MOV(font)]; inqueue[v]=0; for(i=nodevp[v];~i;i=next[i]) { u=nodeu[i]; if(dist[v]+data[i]<dist[u]) { dist[u]=dist[v]+data[i]; if(!inqueue[u]) { queue[MOV(rear)]=u; inqueue[u]=1; } } } } dist[0]=0; for(i=2;i<=n;i++) { if(dist[i]==MAXVAL) return -1; dist[0]+=dist[i]*weight[i]; } return dist[0]; } void addedge(int v,int u,int val) { nodeu[ind]=u; data[ind]=val; next[ind]=nodevp[v]; nodevp[v]=ind++; } void solve() { int i,t,n,m,v,u,val; long long ans=0; scanf("%d",&t); while(t--) { scanf("%d %d",&n,&m); for(i=1;i<=n;i++) { scanf("%d",weight+i); } memset(nodevp,-1,sizeof(nodevp)); ind=0; for(i=1;i<=m;i++) { scanf("%d %d %d",&v,&u,&val); addedge(v,u,val); addedge(u,v,val); } ans=SPFA(1,n); if(ans!=-1) { printf("%lld\n",ans); } else printf("No Answer\n"); } } int main() { freopen("in.txt","r",stdin); solve(); return 0; }