记录编号	608923	评测结果	AAAAAAAAAA
题目名称	4189.Minimum Cost Roads	最终得分	100
用户昵称	会挽弯弓满月	是否通过	通过
代码语言	C++	运行时间	0.686 s
提交时间	2025-10-30 16:24:49	内存使用	3.90 MiB

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll N=2010,inf=1e18;
ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<48||c>57){
		if(c==45) f=-1;
		c=getchar();
	}
	while(c>=48&&c<=57){
		x=(x<<1)+(x<<3)+c-48;
		c=getchar();
	}
	return f*x;
}
ll n,m;
struct qu{
	ll u,v,l,c;
}que[N];
bool cmp(qu a,qu b){
	if(a.l==b.l) return a.c<b.c;
	return a.l<b.l;
}
struct node{
	ll to,nxt,len;
}e[N<<1];
ll h[N],tot;
void add(ll u,ll v,ll l){
	e[++tot]={v,h[u],l};
	h[u]=tot;
	return;
}
ll dis[N];
bool vis[N];
struct edge{
	ll len,id;
	friend bool operator <(const edge &a,const edge &b){
		return a.len>b.len;
	}
};
priority_queue<edge> q;
ll dijkstra(ll st,ll ed){
	while(q.size()) q.pop();
	for(ll i=0;i<=n;i++){
		dis[i]=inf;
		vis[i]=0;
	}
	dis[st]=0;
	q.push((edge){0,st});
	ll u,v,l;
	while(q.size()){
		u=q.top().id;q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(ll i=h[u];i;i=e[i].nxt){
			v=e[i].to;l=e[i].len;
			if(dis[v]>dis[u]+l){
				dis[v]=dis[u]+l;
				q.push((edge){dis[v],v});
			}
		}
	}
	return dis[ed];
}
ll ans;
int main(){
	freopen("Roads.in","r",stdin);
	freopen("Roads.out","w",stdout);
	n=read();m=read();
	for(ll i=1;i<=m;i++)
		que[i]={read(),read(),read(),read()};
	sort(que+1,que+m+1,cmp);
	ll u,v,l,c,k;
	for(ll i=1;i<=m;i++){
		u=que[i].u;v=que[i].v;
		l=que[i].l;c=que[i].c;
		k=dijkstra(u,v);
		if(k>l){
			ans+=c;
			add(u,v,l);
			add(v,u,l);
		}
	}
	printf("%lld",ans);
	return 0;
}