POJ 3013 Big Christmas Tree(最短路Dijkstra+优先队列优化，SPFA)

ACM

题目地址：

题意： 

圣诞树是由n个节点和e个边构成的，点编号1-n。树根为编号1，选择一些边。使得全部节点构成一棵树。选择边的代价是（子孙的点的重量）×（这条边的价值）。

求代价最小多少。

分析： 

单看每一个点被计算过的代价，非常明显就是从根到节点的边的价值。所以这是个简单的单源最短路问题。

只是坑点还是非常多的。

 

点的数量高达5w个，用矩阵存不行。仅仅能用边存。 

还有路径和结果会超int。所以要提高INF的上限。(1<<16)*50000就可以。

能够用Dijkstra+优先队列做，也能够用SPFA做，貌似SPFA会更快。我这里用的是Dijkstra，要1s多...回头要用SPFA做一遍。

用SPFA做了一遍发现也是1s多，看了是STL用多了 = =。 

嘛。留个模板。

代码： 

(Dijkstra+priority_queue)

/**  Author:      illuz 
     
      *  File:        3013.cpp*  Create Date: 2014-07-27 09:54:35*  Descripton:  dijkstra */#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;#include 
          
           #include 
           
            #define repf(i,a,b) for(int i=(a);i<=(b);i++)const int N = 50100;const long long INF = (long long)(1<<16)*N;struct Edge { int from, to; int dist;};struct HeapNode { int d; int u; bool operator < (const HeapNode rhs) const { return d > rhs.d; }};struct Dijkstra { int n, m; // number of nodes and edges vector
            
              edges; vector
             
               G[N]; // graph bool vis[N]; // visited?
             
            
           
          
         
        
       
      
     

long long d[N]; // dis int p[N]; // prevent edge void init(int _n) { n = _n; } void relief() { for (int i = 0; i < n; i++) { G[i].clear(); } edges.clear(); } void AddEdge(int from, int to, int dist) { // if non-directed, add twice edges.push_back((Edge){from, to, dist}); m = edges.size(); G[from].push_back(m - 1); } void dijkstra(int s) { priority_queue<HeapNode> Q; for (int i = 0; i < n; i++) { d[i] = INF; vis[i] = 0; } d[s] = 0; Q.push((HeapNode){0, s}); while (!Q.empty()) { HeapNode x = Q.top(); Q.pop(); int u = x.u; if (vis[u]) { continue; } vis[u] = true; for (int i = 0; i < G[u].size(); i++) { // update the u's linking nodes Edge& e = edges[G[u][i]]; //ref for convenient if (d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; p[e.to] = G[u][i]; Q.push((HeapNode){d[e.to], e.to}); } } } } }; int t; int e, v, x, y, d, w[N]; int main() { scanf("%d", &t); Dijkstra di; while (t--) { scanf("%d%d", &v, &e); di.init(v); repf (i, 0, v - 1) { scanf("%d" ,&w[i]); } repf (i, 0, e - 1) { scanf("%d%d%d", &x, &y, &d); di.AddEdge(x - 1, y - 1, d); di.AddEdge(y - 1, x - 1, d); } di.dijkstra(0); long long ans = 0; bool ring = false; repf (i, 0, v - 1) { if (di.d[i] == INF) { ring = true; } ans += w[i] * di.d[i]; } if (ring) { cout << "No Answer" << endl; } else { cout << ans << endl; } if (t) // if not the last case di.relief(); } return 0; }

(SPFA)

/**  Author:      illuz 
     
      *  File:        3013_spfa.cpp*  Create Date: 2014-07-27 15:44:45*  Descripton:  spfa */#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;#include 
          
           #include 
           
            #define repf(i,a,b) for(int i=(a);i<=(b);i++)const int N = 50100;const long long INF = (long long)(1<<16)*N;struct Edge { int from, to; int spst;};struct SPFA { int n, m; vector
            
              edges; vector
             
               G[N]; // the edges which from i bool vis[N]; long long d[N]; // sps int p[N]; // prevent void init(int _n) { n = _n; } void relief() { for (int i = 0; i < n; i++) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int spst) { // if non-sprected, add twice edges.push_back((Edge){from, to, spst}); m = edges.size(); G[from].push_back(m - 1); } void spfa(int s) { queue
              
                Q; while (!Q.empty()) Q.pop(); for (int i = 0; i < n; i++) { d[i] = INF; vis[i] = 0; } d[s] = 0; vis[s] = 1; Q.push(s); while (!Q.empty()) { int u = Q.front(); Q.pop(); vis[u] = 0; for (int i = 0; i < G[u].size(); i++) { Edge& e = edges[G[u][i]]; if (d[e.to] > d[u] + e.spst) { d[e.to] = d[u] + e.spst; p[e.to] = G[u][i]; if (!vis[e.to]) { vis[e.to] = 1; Q.push(e.to); } } } } }};int t;int e, v, x, y, d, w[N];int main() { scanf("%d", &t); SPFA sp; while (t--) { scanf("%d%d", &v, &e); sp.init(v); repf (i, 0, v - 1) { scanf("%d" ,&w[i]); } repf (i, 0, e - 1) { scanf("%d%d%d", &x, &y, &d); sp.AddEdge(x - 1, y - 1, d); sp.AddEdge(y - 1, x - 1, d); } sp.spfa(0); long long ans = 0; bool ring = false; repf (i, 0, v - 1) { if (sp.d[i] == INF) { ring = true; } ans += w[i] * sp.d[i]; } if (ring) { cout << "No Answer" << endl; } else { cout << ans << endl; } if (t) // if not the last case sp.relief(); } return 0;}
              
             
            
           
          
         
        
       
      
     

版权声明：本文博主原创文章。博客，未经同意不得转载。