原题链接

题解

贪心，我管这种叫做策略贪心，即按照某种顺序或者角度去贪心可以得到最优解

既然题目要求任意两点间最短路最小的同时，价格也最小，那么我们就按长度为第一关键字，花费为第二关键字排序。然后遍历所有边看看这条边能否使用

遍历过程的策略：
如果这条边加入后，这条边两端的节点之间的距离不变。
如果变小了，便加入；此时需不需要去掉某条原先已经加入的边呢？不用，因为每条边都一定是其直接相连两点间长度最短且价格最少的边，不能去掉

code1（TLE）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxs=2e18;
struct node
{
    ll x,y,l,c;
}e[2005];

bool cmp(node a,node b)
{
    if(a.l!=b.l) return a.l<b.l;
    return a.c<b.c;
}

ll dis[2005][2004];
int main()
{
    ll n,m;
    cin>>n>>m;

    for(ll i=1;i<=m;i++)
    {
        cin>>e[i].x>>e[i].y>>e[i].l>>e[i].c;
    }

    sort(e+1,e+1+m,cmp);

    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=n;j++) dis[i][j]=maxs;
    }

    for(ll i=1;i<=n;i++) dis[i][i]=0;
    ll cost=0;
    for(ll i=1;i<=m;i++)
    {
        ll x=e[i].x,y=e[i].y,l=e[i].l,c=e[i].c;
        if(dis[x][y]>l)
        {
            //printf("edge %d:  x:%d y:%d l:%d c:%d \n",i,x,y,l,c);
            dis[x][y]=dis[y][x]=l;
            cost+=c;
            for(ll j=1;j<=n;j++)
            {
                for(ll k=1;k<=n;k++)
                {
                    dis[k][j]=min(dis[k][j],dis[k][x]+dis[y][j]+l);
                    dis[k][j]=min(dis[k][j],dis[k][y]+dis[x][j]+l);
                    dis[j][k]=dis[k][j];
                }
            }
        }
    }

    cout<<cost;
    return 0;
}

优化

考虑优化，发现对于遍历每条边的时候，我们只需要知道这条边两端节点的距离就行了，所以我们可以用 \(O(nlogm)\) 判断+ \(O(1)\) 更新 的最短路算法代替 \(O(1)\) 判断+ \(O(n^2)\) 更新的暴力算法
再度优化，当两个节点没有任何路径相连时，这条边一定加入，这里我们可以通过判断是否位于一个集合处理

总时间复杂度： \(O(m\frac{nlogm+logn}{2})\)

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxs=2e18;
struct node
{
    ll x,y,l,c;
}e[2005];

bool cmp(node a,node b)
{
    if(a.l!=b.l) return a.l<b.l;
    return a.c<b.c;
}


ll fa[2005];
ll finds(ll now)
{
    return now==fa[now]?now:fa[now]=finds(fa[now]);
}

struct unit
{
    ll to,len;
};
vector<unit> G[2005];

struct fresh
{
    ll pos,val;
    bool operator<(const fresh&b) const
    {
        return b.val<val;
    }
};
ll n,m;
bool check(ll s,ll t,ll d)
{
    priority_queue<fresh> q;
    ll dis[2005];
    for(ll i=1;i<=n;i++) dis[i]=maxs;
    q.push({s,0});
    while(q.size())
    {
        ll now=q.top().pos,val=q.top().val;
        q.pop();
        if(now==t) return d<val;
        if(dis[now]<=val) continue;
        dis[now]=val;
        for(auto next:G[now])
        {
            ll to=next.to,len=next.len;
            if(dis[now]+len<dis[to])q.push({to,len+dis[now]});
        }
    }
    return true;
}

int main()
{
    cin>>n>>m;

    for(ll i=1;i<=n;i++) fa[i]=i;

    for(ll i=1;i<=m;i++)
    {
        cin>>e[i].x>>e[i].y>>e[i].l>>e[i].c;
    }

    sort(e+1,e+1+m,cmp);

    ll cost=0;
    for(ll i=1;i<=m;i++)
    {
        ll x=e[i].x,y=e[i].y,l=e[i].l,c=e[i].c;

        if(finds(x)!=finds(y)||check(x,y,l))
        {
            cost+=c;
            G[x].push_back({y,l});
            G[y].push_back({x,l});
            fa[finds(x)]=finds(y);
        }
    }

    cout<<cost;
    return 0;
}