[数据结构与算法]Aizu - 2249 在 最短路 基础上 求此时的最小生成树

题目

链接

题解思路

1e5 不存在 负权 锁定 堆优化迪杰斯特拉来处理最短路
生成树就是每个源点被松弛后加入dis数组所组成的，我们只要在松弛后将每个点提供生成树的值代入即可。

不过还是有特殊条件的，当边等于此时的dis值时，我们要选择较小的花费，此时可以松弛也可以不松弛，对最短距离并没有影响。

最后再累加上每个点提供的生成树值即可。

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

#define INF 0x3f3f3f3f

struct bian
{
    int z,w,l;
    bool operator < (const bian &other) const
    {
        if ( l == other.l )
            return w > other.w;
        return l > other.l;
    }
};
vector <bian> head[10100];

int dis[10100];
int sum[10100];
bool vis[10100];

int n,m;

void djs()
{
    for (int i = 1 ; i <= n ; i++ )
    {
        dis[i] = INF;
        sum[i] = INF;
        vis[i] = 0;
    }
    bian tmm;
    priority_queue <bian> q;
    dis[1] = 0 ;
    sum[1] = 0 ;
    tmm.z = 1 ;
    tmm.l = 0 ;
    tmm.w = 0 ;
    q.push(tmm);
    while(!q.empty())
    {
        bian k;
        k = q.top();
        q.pop();
        if ( vis[k.z])
            continue;
        vis[k.z] = 1;
        int p = k.z ;
        for (int i = 0 ; i < head[p].size() ; i++ )
        {
            bian pit = head[p][i];
            if ( dis[pit.z] >= dis[p] + pit.l )
            {
                if ( dis[pit.z] == dis[p] + pit.l )
                {
                    sum[pit.z] = min(pit.w , sum[pit.z]);
                }else
                    sum[pit.z] = pit.w;
                dis[pit.z] = dis[p] + pit.l;
                bian tp;
                tp.z = pit.z;
                tp.l = dis[pit.z];
                tp.w = sum[pit.z];
                q.push(tp);
            }
        }
    }
    long long  ans = 0 ;
    for (int i = 1 ; i <= n ; i++ )
    {
        ans += sum[i];
        //cout<<dis[i]<<" ";
    }
    cout<<ans<<"\n";
}
int main ()
{
    while(cin>>n>>m)
    {
        if ( !n )
            break;
        for (int i = 1 ; i <= m ; i++ )
        {
            bian tp;
            int t1,t2,t3,t4;
            cin>>t1>>t2>>t3>>t4;
            tp.z = t2;
            tp.l = t3;
            tp.w = t4;
            head[t1].push_back(tp);
            tp.z = t1;
            head[t2].push_back(tp);
        }
        djs();
        for (int i = 1 ; i <= n ; i++ )
            head[i].clear();
    }
    return 0;
}