记录编号	608928	评测结果	AAAAAAAAAA
题目名称	4189.Minimum Cost Roads	最终得分	100
用户昵称	54lku	是否通过	通过
代码语言	C++	运行时间	0.469 s
提交时间	2025-10-30 18:31:23	内存使用	3.82 MiB

#include<bits/stdc++.h>
using namespace std;
long long dist[2001],cost=0;
int bian[4010][3],node[2010],biantot=1;
struct nd
{
	int pos;long long len;
	nd(int a,long long b){pos=a;len=b;}
	bool operator < (const nd & tmp)const
	{
		return len>tmp.len;	
	}	 
};
priority_queue<nd> pq;
bool vis[2010];
struct ed
{
	int u,v;long long l,cost;
	ed(int a,int b,long long c,long long d){u=a;v=b;l=c;this->cost=d;}
	bool operator < (const ed & tmp)const
	{
		if(l==tmp.l)
			return this->cost<tmp.cost;
		return l<tmp.l;
	}
};
inline void link(ed p)
{
	int u=p.u,v=p.v;long long w=p.l;
	bian[biantot][0]=v;
	bian[biantot][1]=w;
	bian[biantot][2]=node[u];
	node[u]=biantot++;
	bian[biantot][0]=u;
	bian[biantot][1]=w;
	bian[biantot][2]=node[v];
	node[v]=biantot++;
	cost+=p.cost;
}
int n,m;
inline void clr()
{
	for(int i=1;i<=n;i++)
		dist[i]=(long long)1e18,vis[i]=0;
	while(!pq.empty())pq.pop();
}
inline long long dij(int u,int v)
{
	clr();
	dist[u]=0;
	pq.push(nd(u,0));
	bool f=0;
	while(!pq.empty())
	{
		nd p=pq.top();
		pq.pop();
		if(p.pos==v)f=1;
		if(vis[p.pos]||f)continue;
		vis[p.pos]=1;
		for(int i=node[p.pos];i;i=bian[i][2])
		{
			if((!vis[bian[i][0]])&&(dist[p.pos]+bian[i][1]<dist[bian[i][0]]))
			{
				dist[bian[i][0]]=dist[p.pos]+bian[i][1];
				pq.push(nd(bian[i][0],dist[bian[i][0]]));
			}
		}
	}
	return dist[v];
}
int main()
{
	freopen("Roads.in","r",stdin);
	freopen("Roads.out","w",stdout);
	cin.tie(0),cout.tie(0)->sync_with_stdio(0);
	cin>>n>>m;
	vector<ed> edge;
	for(int i=1;i<=m;i++)
	{
		int u,v;long long l,c;
		cin>>u>>v>>l>>c;
		edge.emplace_back(ed(u,v,l,c));
	}
	sort(edge.begin(),edge.end());
	for(ed i : edge)
		if(dij(i.u,i.v)>i.l)
			link(i);
	cout<<cost;
	return 0;
}