模板

意甲冠军：给你一个图，1始终根，每一方都有单价值，每个点都有权重新。

每个边缘的价格值 = sum（后继结点重)*单价方值。

最低价格要求树值，它构成了一棵树n-1条边的最小价值。

算法：

1、由于每一个边的价值都要乘以后来訪问的节点的权重。而走到后来訪问的点必经过这条边。

实际上总价值就是  到每一个点的最短路径*这个点的权重。

2、可是这个题 数据量真的太大了。50000个点，50000条边。

写普通的dij算法tle。

必须加优先队列优化- -

据说spfa也能过。可是spfa算法不稳定- -，一般没有负权，则用优先队列或堆优化的dijkstra算法

应该能解决这个问题。

3、坑点：点为0或者1时，价值为0，要特判。否则也会tle。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define maxn 50010const __int64 INF = 10000000000;using namespace std;struct node{    int to,next,val;}edge[maxn*2];int v,head[maxn],c[maxn],cnt;long long dis[maxn];bool vis[maxn];typedef pair
          
            PII;priority_queue
           
             ,greater
            
              > q;void add(int x,int y,int z){ edge[cnt].to = y; edge[cnt].val = z; edge[cnt].next = head[x]; head[x] = cnt++;}long long dij(){ for(int i=2;i<=v;i++) dis[i] = INF; while(!q.empty()) q.pop(); int sum = 0; long long ret = 0; long long x; int y; dis[1] = 0; q.push(make_pair(dis[1],1)); while(!q.empty()) { PII cur = q.top(); q.pop(); x = cur.first; y = cur.second; if(vis[y]) continue; vis[y] = true; sum++; ret += x*c[y]; for(int i=head[y];i!=-1;i=edge[i].next) { int u = edge[i].to,p = edge[i].val; if(dis[u]>dis[y]+p) { dis[u] = dis[y]+p; q.push(make_pair(dis[u],u)); } } } if(sum
            
           
          
         
        
       
      
     

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