1924 - 圣诞树
时间限制 : 1 秒
内存限制 : 128 MB
KFC为了迎接圣诞节的到来，员工们打算准备一个大大的圣诞树。圣诞树的结构示意图如下图所示：
这颗圣诞树可以用一些结点和边来表示。结点的编号为1至n。树根的结点总是编号为1的结点。在树中每个结点有自己的重量。这些重量可以看作是互不相同的。因此每条边也可看作是不一样的，即各边的的单价也就不一样了。一条边的价格是它的所有子结点的重量总和×该边的单价。
员工们想花费最少的钱来准备这棵圣诞树。所有结点都是要被用进的。现在他们想请你帮忙来解决这个问题。
题目输入
第一行包含两个整数v和e(1 < = v，e < = 50000)，分别表示节点和边的数目。紧接下面一行包含v个正整数，表示编号1到n的结点重量，再下面e行，每一行三个正整数xi，yi，vi，表示边(xi,yi)的单价为vi。(所有数据都不超过2^16)
题目输出
输出一个整数表示准备这个圣诞树的可能的最小价格。如果没有办法将所有结点用进，输出“No Answer”。
输入/输出样例
输入格式
7 7 200 10 20 30 40 50 60 1 2 1 2 3 3 2 4 2 3 5 4 3 7 2 3 6 3 1 5 9
输出格式
1210
C++解答
/*所求答案是 西格玛(price[i]*西格玛(i的子孙的weight))，可以变换为 西格玛(weight[i]*dist[i]).price 是边的单价，dist是点到根的最短路。weight是点的重量。 因为对于每个点，他前面的边在算价钱的时候都要算到他，所以求最短路 使答案最小。 一个点无法到达时，输出no answer。 数据超大，dijkstra+heap 2.7秒 */ #include<stdio.h> #include<string.h> const int N = 50008; const long long INF = 1111111; struct HEAP { long long data; int num; }; struct NODE { long long data; int num; int next; }; struct DIJ { long long data; int next,last; //qian,hou; int vis; }; HEAP heap[N*2]; NODE list[N*2]; DIJ dis[N*2]; long long w[N*2]; int hash[N*2]; int e,v; int hsize,next; void csh() { int i; memset(w,0,sizeof(w)); memset(hash,0,sizeof(hash)); next = hsize = 0; for(i=0;i<v;i++) { dis[i].data = INF; dis[i].next = -1; dis[i].vis = 0; } } void insert(int x,int y,long long p) { list[next].data = p; list[next].next = -1; list[next].num = y; next++; if(dis[x].next == -1) dis[x].next = next - 1; else list[dis[x].last].next = next - 1; dis[x].last = next - 1; } void swap(int x,int y) { struct temp { long long data; int num; }tmp; tmp.data = heap[x].data; tmp.num = heap[x].num; heap[x].data = heap[y].data; heap[x].num = heap[y].num; heap[y].data = tmp.data; heap[y].num = tmp.num; } void sift_up(int k) { while(k > 0 && heap[(k-1)/2].data > heap[k].data) { hash[heap[k].num] = (k-1) / 2; hash[heap[(k-1)/2].num] = k; swap(k,(k-1)/2); k = (k-1) / 2; } } void sift_down(int k) { int flag = 0; while(k < hsize && !flag) { int l = k*2 + 1; int r = k*2 + 2; int t = -1; flag = 1; if(r < hsize) { if(heap[l].data <= heap[r].data) t = l; else t = r; } else if(l < hsize) t = l; if(t != -1 && (heap[t].data < heap[k].data)) { hash[heap[k].num] = t; hash[heap[t].num] = k; swap(k,t); k = t; flag = 0; } } } void dijkstra_heap(int s,int en) { int i,mark,tmp,k,j; long long min,d; dis[s].data = 0; for(i=0;i<en;i++) { heap[hsize].data = dis[i].data; heap[hsize].num = i; hsize++; hash[i] = hsize-1; sift_up(hsize-1); } for(i=0;i<en-1;i++) { min = heap[0].data; mark = heap[0].num; if(min == INF) return ; dis[mark].vis = 1; tmp = heap[hsize-1].num; hash[tmp] = 0; hash[mark] = hsize - 1; swap(0,hsize - 1); hsize--; sift_up(hash[tmp]); sift_down(hash[tmp]); for(j=dis[mark].next;j!=-1;j=list[j].next) { k = list[j].num; d = dis[mark].data + list[j].data; if(d < dis[k].data) { dis[k].data = d; heap[hash[k]].data = d; sift_up(hash[k]); } } } } int main() { //freopen("Christmas.in", "r", stdin); //freopen("Christmas.out", "w", stdout); int i,j,x,y,t,flag; long long sum,p; // scanf("%d",&t); // while(t--) // { scanf("%d%d",&v,&e); csh(); for(i=0;i<v;i++) scanf("%lld",&w[i]); for(i=0;i<e;i++) { scanf("%d%d%lld",&x,&y,&p); x--;y--; if(x != y) { insert(x,y,p); insert(y,x,p); } } dijkstra_heap(0,v); flag = sum = 0; for(i=0;i<v;i++) { if(dis[i].data == INF) { flag = 1; break; } sum += w[i] * dis[i].data; } if(flag) printf("No Answer\n"); else printf("%lld\n",sum); // } return 0; }