POJ3013-Big Christmas Tree-最短路-白红宇

POJ3013-Big Christmas Tree-最短路

阅读量：5327 次

发布时间：2019-06-14

本文共 2207 字，大约阅读时间需要 7 分钟。

题意：给出一个图，每个节点都有权值，每条边也有费用。要求建立一颗树，使总花费最小。树上每连一条边的花费定义为孩子节点权值和×此边费用。

做法：分析可知，最终的答案为所有节点的权值×到根节点的距离。可以知道当距离最短时，花费最小。

　　　于是用Dijkstra+优先队列优化就可以搞定了。这题有些卡时间。最后还要注意使用long long，特判n=0和n=1。

1 /*--------------------------------------------------------------------------------------*/  2 //        Helica's header   3 //        Second Edition  4 //        2015.11.7  5 //  6 #include 
     
        7 #include 
      
         8 #include 
       
          9 #include 
        
          10 #include 
         
           11 #include 
          
            12 #include 
           
             13 #include 
            
              14 #include 
             
               15 #include 
              
                16 #include 
               
                 17 #include 
                
                  18 #include 
                  19 20 //debug function for a N*M array 21 #define debug_map(N,M,G) printf("\n");for(int i=0;i<(N);i++)\ 22 { for(int j=0;j<(M);j++){\ 23 printf("%d",G[i][j]);}printf("\n");} 24 //debug function for int,float,double,etc. 25 #define debug_var(X) cout<<#X"="<
                  
                   <
                   
                    r.c;} 39 }; 40 41 struct Edge 42 { 43 int to,next; 44 int cost; 45 }edge[4*maxn]; 46 47 int head[maxn],tol,weight[maxn]; 48 long long dis[maxn]; 49 bool vis[maxn]; 50 priority_queue
                    
                      que; 51 52 void Dijkstra(int n,int start) 53 { 54 memset(vis,false,sizeof vis); 55 for(int i=1;i<=n;i++) dis[i] = INF; 56 dis[start] = 0; 57 while(!que.empty()) que.pop(); 58 59 que.push(qnode(start,0)); 60 qnode cur; 61 while(!que.empty()) 62 { 63 cur = que.top(); 64 que.pop(); 65 int u = cur.v; 66 if(vis[u]) continue; 67 vis[u] = true; 68 69 for(int i=head[u];~i;i=edge[i].next) 70 { 71 int v = edge[i].to; 72 int cost = edge[i].cost; 73 //printf("u:%d v:%d cost:%d\n",u,v,cost); 74 if(!vis[v] && dis[v]>dis[u]+cost) 75 { 76 dis[v] = dis[u]+cost; 77 que.push(qnode(v,dis[v])); 78 } 79 } 80 } 81 } 82 83 void add_edge(int u,int v,int cost) 84 { 85 edge[tol].to = u; 86 edge[tol].next = head[v]; 87 edge[tol].cost = cost; 88 head[v] = tol++; 89 90 edge[tol].to = v; 91 edge[tol].next = head[u]; 92 edge[tol].cost = cost; 93 head[u] = tol++; 94 } 95 96 int main() 97 { 98 scanf("%d",&T); 99 while(T--)100 {101 scanf("%d%d",&N,&M);102 for(int i=1;i<=N;i++) scanf("%d",&weight[i]);103 memset(head,-1,sizeof head);104 memset(vis,false,sizeof vis);105 tol = 0;106 for(int i=0;i