poj 3031 Big Christmas Tree(水spfa) - c++编程基础

题意：

Because of a technical difficulty, price of an edge will be (sum of weights of all descendant nodes) × (unit price of the edge).这句话一直没看懂。后面还以为是最小生成树。

正确题意是：给一个无向图，计算每个点到1节点的最短路径(dis[i]) * 每个节点的weights之和。

注意：边权值等要用__int64;无向图；

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include
       #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #define LL long long #define _LL __int64 using namespace std; const _LL INF = 1e18; const int maxn = 50010; const int maxm = 50010; struct node { int v; _LL w; int next; }edge[2*maxm]; int cnt,head[maxn]; _LL W[maxn]; int n,m; _LL ans,dis[maxn]; void init() { cnt = 0; memset(head,-1,sizeof(head)); } void add(int u, int v, _LL w) { edge[cnt] = (struct node){v,w,head[u]}; head[u] = cnt++; } void solve() { int inque[maxn]; queue 
            
              que; while(!que.empty()) que.pop(); memset(inque,0,sizeof(inque)); for(int i = 1; i <= n; i++) dis[i] = INF; dis[1] = 0; inque[1] = 1; que.push(1); while(!que.empty()) { int u = que.front(); que.pop(); inque[u] = 0; for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; _LL w = edge[i].w; if(dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if(!inque[v]) { inque[v] = 1; que.push(v); } } } } } int main() { int test; int u,v; _LL w; scanf(%d,&test); while(test--) { init(); scanf(%d %d,&n,&m); for(int i = 1; i <= n; i++) scanf(%I64d,&W[i]); for(int i = 1; i <= m; i++) { scanf(%d %d %I64d,&u,&v,&w); add(u,v,w); add(v,u,w); } solve(); ans = 0; bool flag = true; for(int i = 2; i <= n; i++) { if(dis[i] == INF) { flag = false; break; } ans += dis[i] * W[i]; } if(flag == false) printf(No Answer ); else printf(%I64d ,ans); } return 0; }