AOJ 2249 Road Construction（Dijkstra+优先队列）-白红宇

AOJ 2249 Road Construction（Dijkstra+优先队列）

阅读量：4654 次

发布时间：2019-06-09

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

【题目大意】

　　一张无向图，建造每条道路需要的费用已经给出，

　　现在求在起点到每个点都是最短路的情况下的最小修路费用

【题解】

　　考虑到最后的图一定是树形的，因此只要保留每个点与其父节点之间的边的费用最小值即可

　　在计算最短路的同时不断更新费用

【代码】

#include 
     
        #include 
      
        #include 
       
         #include 
        
          using namespace std;  const int N=2000100;  const int INF=~0U>>2;  typedef pair
         
          seg;  priority_queue
          
           
            ,greater
            
              >q; int d[N],D[N],head[N],u[N],v[N],w[N],nxt[N],cost[N],n,m,a,b,c,cc,ed=0,H,x[N],y[N]; bool vis[N]; void add(int a,int b,int c,int cos){ u[++ed]=a,v[ed]=b,w[ed]=c;cost[ed]=cos; nxt[ed]=head[u[ed]]; head[u[ed]]=ed; } void Dijkstra(int src){ memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++)d[i]=INF; d[src]=0; q.push(make_pair(d[src],src)); while(!q.empty()){ seg now=q.top(); q.pop(); int x=now.second; if(d[x]
             
              d[x]+w[e]){ d[v[e]]=d[x]+w[e]; D[v[e]]=cost[e]; q.push(make_pair(d[v[e]],v[e])); }else if(d[v[e]]==d[x]+w[e]){ D[v[e]]=min(cost[e],D[v[e]]); } }} int main(){ while(~scanf("%d%d",&n,&m),m+n){ memset(head,-1,sizeof(head));ed=0; memset(nxt,-1,sizeof(nxt)); while(m--){ scanf("%d%d%d%d",&a,&b,&c,&cc); add(a,b,c,cc);add(b,a,c,cc); }Dijkstra(1); int ans=0; for(int i=2;i<=n;i++)ans+=D[i]; printf("%d\n",ans); }return 0;}