QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#301289#5054. City Brainzzuqy#WA 7ms101868kbC++142.3kb2024-01-09 17:18:502024-01-09 17:18:50

Judging History

你现在查看的是最新测评结果

  • [2024-01-09 17:18:50]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:101868kb
  • [2024-01-09 17:18:50]
  • 提交

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);
		}
	}
}

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;
	for (int ta = 1; ta <= (kt - b) / a; ta++) {
		int tb = (kt - ta * a) / b;
		assert(tb >= 1 && a * ta + b * tb <= kt);
		//cout << ta << " " << ta << endl;
		double tmp = 1.0 * a / ta + 2.0 * b / tb;
		{
			if (kt - a * ta - b * tb >= a)
				continue;
			ans = min(ans, tmp - (kt - a * ta - b * tb) * 1.0 / ta / (ta + 1));
		}
		{
			if (kt - a * ta - b * tb >= b)
				continue;
			ans = min(ans, 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 100000
1 2
3 2
2 4
4 5
4 6
1 5 2 6
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 101772kb

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: 7ms
memory: 101764kb

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: 7ms
memory: 101768kb

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: 3ms
memory: 101868kb

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'