Submission #1194436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194436		lyh0217	Farm and factory (CERC12_F)	C++20	1 / 1	729 ms	36484 KiB

F

#include<bits/stdc++.h>
using namespace std;
long long dis1[100005],dis2[100005];
bool vis[100005];
struct stu{
	int x,w;
};
long long a[100005],b[100005];
vector<stu>v[100005];
struct stu2{
	long long x,w;
	inline bool friend operator<(stu2 const &a,stu2 const &b)
	{
		return a.w>b.w;
	}
};
priority_queue<stu2>q;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++) 
		{
			v[i].clear();
		}
		memset(dis1,0x3f,sizeof(dis1));
		memset(dis2,0x3f,sizeof(dis2));
		for(int i=1;i<=m;i++)
		{
			int x,y,w;
			cin>>x>>y>>w;
			v[x].push_back({y,w});
			v[y].push_back({x,w});
		}
		dis1[1]=0;
		q.push({1,0});
		while(!q.empty())
		{
			int x=q.top().x;
			q.pop();
			vis[x]=0;
			for(auto i:v[x])
			{
				if(dis1[i.x]>dis1[x]+i.w)
				{
					dis1[i.x]=dis1[x]+i.w;
					if(!vis[i.x])
					{
						vis[i.x]=1;
						q.push({i.x,dis1[i.x]});
					}
				}
			}
		}
		dis2[2]=0;
		q.push({2,0});
		while(!q.empty())
		{
			int x=q.top().x;
			q.pop();
			vis[x]=0;
			for(auto i:v[x])
			{
				if(dis2[i.x]>dis2[x]+i.w)
				{
					dis2[i.x]=dis2[x]+i.w;
					if(!vis[i.x])
					{
						vis[i.x]=1;
						q.push({i.x,dis2[i.x]});
					}
				}
			}
		}
		for(int i=1;i<=n;i++) 
		{
			a[i]=dis1[i]+dis2[i];
			b[i]=dis1[i]-dis2[i];
		}
		sort(a+1,a+n+1);
		sort(b+1,b+n+1);
		long long sum=0;
		long long xx=a[(n+1)/2],yy=b[(n+1)/2];
		for(int i=1;i<=n;i++)
		{
			sum+=abs(xx-a[i])+abs(yy-b[i]);
		}
		printf("%.9lf\n",1.0*sum/(2.0*n));
	}
	return 0;
}

• Subtask 1: 1 / 1