QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #301181 | #5054. City Brain | zzuqy# | WA | 12ms | 102128kb | C++14 | 3.0kb | 2024-01-09 15:50:55 | 2024-01-09 15:50:55 |
Judging History
answer
#include <bits/stdc++.h>
#define N 5009
using namespace std;
vector<int>to[N];
int n, m, k;
int d[N][N];
void bfs(int st) {
queue<int>q;
q.push(st);
d[st][st] = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
for (auto y : to[x]) {
if (d[st][y] != 1000000000)
continue;
d[st][y] = d[st][x] + 1;
q.push(y);
}
}
}
long double s2 = 1.414213562373095048;
double calc(int a, int b, int kt) {
if (a == 0 && b == 0)
return 0;
kt += a + b;
if (b == 0)
return 1.0 * (kt % a) / (kt / a + 1) + 1.0 * (a - kt % a) / (kt / a);
if (a == 0)
return 2.0 * (kt % b) / (kt / b + 1) + 2.0 * (b - kt % b) / (kt / b);
double ans = 1000000000;
if (a >= b) {
int ttmp = (int)(kt / (a + s2 * b));
for (int ta = max(ttmp - n, 1); ta <= min((kt - b) / a, ttmp + n); ta++) {
int tb = (kt - ta * a) / b;
//cout << ta << " " << ta << endl;
double tmp = 1.0 * a / ta + 2.0 * b / tb;
if (1ll * tb * (tb + 1) > 2ll * ta * (ta + 1)) {
if (kt - a * ta - b * tb >= a)
assert(0);
tmp -= (kt - a * ta - b * tb) * 1.0 / ta / (ta + 1);
} else {
if (kt - a * ta - b * tb >= b)
assert(0);
tmp -= (kt - a * ta - b * tb) * 2.0 / tb / (tb + 1);
//flag |= 2;
}
if (tmp < ans)
ans = tmp;
}
} else {
int ttmp = (int)(kt / (a + s2 * b) * s2);
for (int tb = max(ttmp - n, 1); tb <= min((kt - a) / b, ttmp + n); tb++) {
int ta = (kt - tb * b) / a;
//cout << ta << " " << ta << endl;
double tmp = 1.0 * a / ta + 2.0 * b / tb;
if (1ll * tb * (tb + 1) > 2ll * ta * (ta + 1)) {
if (kt - a * ta - b * tb >= a)
assert(0);
tmp -= (kt - a * ta - b * tb) * 1.0 / ta / (ta + 1);
} else {
if (kt - a * ta - b * tb >= b)
assert(0);
tmp -= (kt - a * ta - b * tb) * 2.0 / tb / (tb + 1);
//flag |= 2;
}
if (tmp < ans)
ans = tmp;
}
}
//cout << 1.0 * mntb / mnta << endl;
return ans;
}
int mn[N];
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
to[a].push_back(b);
to[b].push_back(a);
}
fill(d[0], d[0] + N * N, 1000000000);
for (int i = 1; i <= n; i++)
bfs(i);
/*
for (int i = 1; i <= n; i++, cout << endl)
for (int j = 1; j <= n; j++)
cout << d[i][j] << " ";
*/
int s1, t1, s2, t2;
cin >> s1 >> t1 >> s2 >> t2;
fill(mn, mn + N, 1000000000);
mn[0] = d[s1][t1] + d[s2][t2];
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
if (d[s1][a] == 1000000000 || d[b][t1] == 1000000000 || d[a][b] == 1000000000)
continue;
if (d[s2][a] == 1000000000 || d[b][t2] == 1000000000)
continue;
mn[d[a][b]] = min(mn[d[a][b]], d[s1][a] + d[b][t1] + d[s2][a] + d[b][t2]);
}
}
double ans = 1000000000;
for (int i = 0; i <= n; i++) {
if (mn[i] == 1000000000)
continue;
//0cout << mn[i] << " " << i << " " << calc(mn[i], i, k) << endl;
ans = min(ans, calc(mn[i], i, k));
}
cout << fixed << setprecision(15) << ans;
}
/*
6 5 1
1 2
3 2
2 4
4 5
4 6
1 5 3 6
*/
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 101936kb
input:
6 5 1 1 2 3 2 2 4 4 5 4 6 1 5 3 6
output:
5.000000000000000
result:
ok found '5.000000000', expected '5.000000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 12ms
memory: 101936kb
input:
1 0 100 1 1 1 1
output:
0.000000000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 102064kb
input:
4 2 3 1 2 3 4 1 2 3 4
output:
0.833333333333333
result:
ok found '0.833333333', expected '0.833333333', error '0.000000000'
Test #4:
score: -100
Wrong Answer
time: 4ms
memory: 102128kb
input:
6 5 1 1 2 3 2 2 4 4 5 4 6 1 5 6 3
output:
5.500000000000000
result:
wrong answer 1st numbers differ - expected: '5.0000000', found: '5.5000000', error = '0.1000000'