#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
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);
| ~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
258 ms |
5460 KB |
Output is correct |
| 3 |
Correct |
914 ms |
97480 KB |
Output is correct |
