Submission #843691

#	Time	Username	Problem	Language	Result	Execution time	Memory
843691		vjudge1	Farm and factory (CERC12_F)	C++14	1 / 1	914 ms	97480 KiB

F

#include <bits/stdc++.h>
#include <queue>
#include <vector>
#define db long double
#define int long long
using namespace std;
const int N = 1e5+5;
inline int read() ;
int n, m;
struct node {
	int v,w;
	friend bool operator < (node fi,node se) {
		return fi.w>se.w;
	}
};
vector<node > lj[N];
int f[N],g[N];
int x[N];
bitset<N > vis;
priority_queue<node > q;
inline void spfa(int st,int dis[N]) {
	dis[st]=0;
	while(!q.empty()) q.pop();
	q.push(<%st,0%>);
	vis=0;
	while(!q.empty()) {
		int now=q.top().v;
		q.pop();
		if(vis[now]) continue;
		vis[now]=1;
		for(int i=0;i<lj[now].size();++i) {
			node it=lj[now][i];
			int to=it.v,w=it.w;
			if(dis[to]>dis[now]+w) {
				dis[to]=dis[now]+w;
				q.push(<%to,dis[to]%>);
			}
		}
	}
//	for(int i=1; i<=n; ++i) cout<<dis[i]<<" ";cout<<endl;
}
inline void solve() {
	n=read(),m=read();
	for(int i=1; i<=m; ++i) {
		int u=read(),v=read(),w=read();
		lj[u].push_back(<%v,w%>),lj[v].push_back(<%u,w%>);
	}
	memset(f,0x3f,sizeof f);
	memset(g,0x3f,sizeof g);
	spfa(1,f),spfa(2,g);
	for(int i=1; i<=n; ++i) x[i]=(f[i]+g[i]);
	sort(x+1,x+n+1);
	int ans=0;
	for(int i=1; i<=n/2; ++i) ans+=(abs(x[n-i+1]-x[i]));
	for(int i=1; i<=n; ++i) x[i]=(f[i]-g[i]);
	sort(x+1,x+n+1);
//	for(int i=1; i<=n; ++i) cout<<x[i]<<" ";cout<<endl;
	for(int i=1; i<=n/2; ++i) ans+=(abs(x[n-i+1]-x[i]));
	printf("%.12Lf\n",(db)ans/n/2);
	for(int i=1; i<=n; ++i) lj[i].clear();
}
signed main() {
	int T=read();
	while(T--) solve();
	return 0;
}

inline int read() {
	int x;
	scanf("%lld",&x);
	return x;
}

Compilation message (stderr)

F.cpp: In function 'void spfa(long long int, long long int*)':
F.cpp:31:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for(int i=0;i<lj[now].size();++i) {
      |               ~^~~~~~~~~~~~~~~
F.cpp: In function 'long long int read()':
F.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |  scanf("%lld",&x);
      |  ~~~~~^~~~~~~~~~~

• Subtask 1: 1 / 1