#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define rb(x) ((x)&(-(x)))
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
const int MAXN = 100055;
const int MAXM = 300055;
ll dp[2][MAXN];
vector<int> G[MAXN];
int A[MAXM], B[MAXM], C[MAXM];
int T, N, M;
void runDijk(ll dp[], int sidx) {
fill(dp, dp+N+1, INFLL);
dp[sidx] = 0;
priority_queue<pli, vector<pli>, greater<pli>> PQ;
PQ.emplace(0, sidx);
for(ll dst; !PQ.empty();) {
int idx; tie(dst, idx) = PQ.top(); PQ.pop();
if(dp[idx] < dst) continue;
for(int e : G[idx]) {
int v = A[e]^B[e]^idx;
ll ndst = dst + C[e];
if(dp[v] <= ndst) continue;
dp[v] = ndst;
PQ.emplace(ndst, v);
}
}
}
void run() {
cin >> N >> M;
for(int i = 1; i <= M; i++) {
cin >> A[i] >> B[i] >> C[i];
G[A[i]].eb(i);
G[B[i]].eb(i);
}
runDijk(dp[0], 1); runDijk(dp[1], 2);
vector<ll> AV, BV;
for(int i = 1; i <= N; i++) {
AV.eb(dp[0][i] + dp[1][i]);
BV.eb(dp[0][i] - dp[1][i]);
}
sorv(AV); sorv(BV);
ll a = AV[N>>1], b = BV[N>>1], sum = dp[0][2];
ld x = ld(a+b) / 2, y = ld(a-b) / 2;
if(x+y < sum) y = sum-x;
ld ret = 0;
for(int i = 1; i <= N; i++)
ret += max(abs(dp[0][i] - x), abs(dp[1][i] - y));
printf("%.20Lf\n", ld(ret) / N);
return;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
for(cin >> T; T--;) run();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Incorrect |
2677 ms |
3952 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
