记录编号	608913	评测结果	AAAAAAAAAA
题目名称	4189.Minimum Cost Roads	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	0.427 s
提交时间	2025-10-30 15:35:17	内存使用	3.78 MiB

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;

const int MAXN = 2005;
const long long INF = 0x3f3f3f3f3f3f3f3f;

struct NODE{
    int u, v, l;
    long long c;
}E[MAXN << 1];
struct node{
    int to, next, len;
}e[MAXN << 1];
long long dis[MAXN];
int h[MAXN], tot = 0;
void add(int x, int y, int len){
    e[++ tot] = {y, h[x], len};
    h[x] = tot;
}
int n, m;
int f[MAXN];
int fd(int x){
    return (x == f[x]) ? x : f[x] = fd(f[x]);
}

bool check(int u, int v, int l){
    memset(dis, 0x3f, sizeof(dis));
    dis[u] = 0;
    priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > q;
    q.push({0, u});
    while(!q.empty()){
    	auto it = q.top(); q.pop();
    	long long d = it.first;
    	int now = it.second;
        if(now == v) break;
        if(d > dis[now]) continue;
        for(int i = h[now];i;i = e[i].next){
            int to = e[i].to, len = e[i].len;
            if(dis[to] > dis[now] + len){
                dis[to] = dis[now] + len;
                q.push({dis[to], to});
            }
        }
    }
    return l < dis[v];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= m;i ++){
        cin >> E[i].u >> E[i].v >> E[i].l >> E[i].c;
    }
    sort(E + 1, E + m + 1, [](const NODE& a, const NODE& b) {
        if(a.l == b.l) return a.c < b.c;
        return a.l < b.l;
    });
    for(int i = 1;i <= n;i ++){
        f[i] = i;
    }
    long long ans = 0;
    for(int i = 1;i <= m;i ++){
        int u = E[i].u, v = E[i].v, l = E[i].l;
        long long c = E[i].c;
        int fx = fd(u), fy = fd(v);
        if(fx != fy){
            f[fx] = fy; ans += c;
            add(u, v, l); add(v, u, l);
        }
        else if(check(u, v, l)){
            ans += c;
            add(u, v, l); add(v, u, l);
        }
    }
    cout << ans << '\n';
    return 0;
}