2 1 1 2 1
General
→ Source
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cassert>
#include<vector>
#include<set>
#include<cmath>
#include<map>
#include<queue>
#include<cstring>
#define fi first
#define se second
#define mp make_pair
#define FOR(i, n) for(int i = 0; i < n; ++i)
using namespace std;
const int N = 1e5 + 2;
const double eps = 1e-11;
typedef long double lf;
int f[303][303];
int n, m, sz;
pair<int, int> p[303];
lf ret = 1e11;
lf calc(lf x, lf dis, int t)
{
dis = max(dis - x, x);
for(int i = 0; i < sz; ++i)
{
dis = max(dis, min(p[i].fi + x, p[i].se - x + t));
}
return dis;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
FOR(i, n) FOR(j, i) f[i][j] = f[j][i] = 1 << 29;
FOR(i, m)
{
int x, y, d;
cin >> x >> y >> d;
--x, --y;
f[x][y] = f[y][x] = d;
}
FOR(k, n) FOR(i, n) FOR(j, n) f[i][j] = min(f[i][k] + f[k][j], f[i][j]);
FOR(i, n){
lf d = 0;
FOR(j, n)
if(i != j)
{
d = max(d, (lf)f[i][j]);
int dis = f[i][j];
sz = 0;
FOR(k, n)
if(i != k && j != k)
{
p[sz++] = make_pair(f[i][k], f[j][k]);
}
if(dis == f[i][j] && sz == 0)
{
ret = min(ret, (lf)(f[i][j] / 2.0));
continue;
}
lf l = 0, r = f[i][j], mid, mdmd;
while(r - l > eps)
{
mid = (l + r) / 2;
mdmd = (mid + r) / 2;
if(calc(mid, dis, f[i][j]) > calc(mdmd, dis, f[i][j])) l = mid;
else r = mdmd;
}
ret = min(ret, min(calc(mid, dis, f[i][j]), calc(mdmd, dis, f[i][j])));
}
ret = min(ret, d);
}
cout.precision(11);
cout.setf( ios::fixed );
cout << ret << endl;
return 0;
}
1
Input
Participant's output
0.50000000000
Jury's answer
0.50
Checker comment
2
Input
3 3 1 2 1 2 3 1 1 3 1
Participant's output
1.00000000000
Jury's answer
1.00
Checker comment
ok found '1.000000000', expected '1.000000000', error '0.000000000'
3
Input
3 2 1 2 100 2 3 1
Participant's output
50.50000000000
Jury's answer
50.50
Checker comment
ok found '50.500000000', expected '50.500000000', error '0.000000000'
4
Input
2 1 1 2 100000
Participant's output
50000.00000000000
Jury's answer
50000.00
Checker comment
ok found '50000.000000000', expected '50000.000000000', error '0.000000000'
5
Input
4 3 2 3 9 3 1 9 4 3 4
Participant's output
9.00000000000
Jury's answer
9.00
Checker comment
ok found '9.000000000', expected '9.000000000', error '0.000000000'
6
Input
4 4 3 4 10 2 4 6 2 3 9 4 1 7
Participant's output
8.50000000000
Jury's answer
8.50
Checker comment
ok found '8.500000000', expected '8.500000000', error '0.000000000'
7
Input
5 6 4 1 8 2 1 7 3 2 5 4 5 5 3 1 2 2 4 5
Participant's output
7.50000000000
Jury's answer
7.50
Checker comment
ok found '7.500000000', expected '7.500000000', error '0.000000000'
8
Input
5 8 5 3 8 2 5 2 3 4 4 2 4 9 1 2 10 4 5 1 5 1 10 3 1 9
Participant's output
7.50000000000
Jury's answer
7.50
Checker comment
ok found '7.500000000', expected '7.500000000', error '0.000000000'
9
Input
200 10000 27 68 11134 70 161 99726 157 142 70479 182 14 2019 138 16 40035 186 119 19663 64 144 7895 140 177 43300 13 198 60937 100 55 88496 68 118 20536 192 99 50436 176 21 78615 120 63 9798 37 6 17485 57 44 26773 188 79 64300 134 54 414...
Participant's output
8125.00000000000
Jury's answer
8125.00
Checker comment
ok found '8125.000000000', expected '8125.000000000', error '0.000000000'
10
Input
50 500 17 9 30352 17 29 43716 38 13 81511 38 40 4601 4 12 18180 30 19 611 47 6 93013 18 2 80749 50 11 60139 28 33 34504 23 4 28778 46 26 75826 3 25 38656 2 50 37844 37 23 43859 24 10 39526 2 5 7250 25 19 75053 42 16 94093 7 35 64389 2...
Participant's output
33606.00000000000
Jury's answer
33606.00
Checker comment
ok found '33606.000000000', expected '33606.000000000', error '0.000000000'
11
Input
100 1000 37 13 53017 42 72 37771 10 44 69652 12 26 84977 45 1 76516 94 13 9292 82 24 75941 33 88 49525 35 29 46258 56 68 35961 6 21 19136 93 71 81066 94 52 55127 30 71 5605 70 3 23822 84 46 18720 18 36 21090 33 3 68912 76 43 62866 98 5...
Participant's output
43826.00000000000
Jury's answer
43826.00
Checker comment
ok found '43826.000000000', expected '43826.000000000', error '0.000000000'
12
Input
100 4000 84 11 63955 55 45 2918 1 62 21403 93 72 21058 2 24 32634 85 44 81847 27 36 24277 39 28 58015 66 19 67123 29 23 44826 50 97 46284 97 62 90988 91 82 92826 70 65 32322 9 45 32780 31 56 55058 46 40 50362 18 70 6784 89 76 42322 23 ...
Participant's output
7603.00000000000
Jury's answer
7603.00
Checker comment
ok found '7603.000000000', expected '7603.000000000', error '0.000000000'
13
Input
200 1000 132 168 99553 139 117 91814 11 187 68971 149 60 19399 9 37 92216 74 174 24012 27 123 70736 4 194 22778 101 134 44570 5 118 94836 166 193 4740 21 52 46322 16 140 89887 152 79 31433 28 15 90343 166 143 43562 181 197 52609 166 70 7...
Participant's output
81601.00000000000
Jury's answer
81601.00
Checker comment
ok found '81601.000000000', expected '81601.000000000', error '0.000000000'
14
Input
200 5000 176 179 57135 124 108 63261 53 29 39007 93 116 66265 40 39 60974 10 63 53179 12 186 11866 37 69 68115 46 32 42311 138 108 33487 169 97 57658 74 126 53965 92 120 60737 101 115 46577 67 132 24048 85 130 50482 105 123 55174 17 63 5...
Participant's output
15437.50000000000
Jury's answer
15437.50
Checker comment
ok found '15437.500000000', expected '15437.500000000', error '0.000000000'
15
Input
100 4950 4 97 48187 58 72 93264 30 94 59682 9 78 10216 57 60 13811 81 76 41010 72 70 11520 100 53 80894 39 25 30392 59 62 2347 59 80 45012 41 43 89162 13 11 3466 34 42 11962 86 82 88767 94 51 91762 61 27 27706 45 16 35294 47 37 97043 3...
Participant's output
7982.50000000000
Jury's answer
7982.50
Checker comment
ok found '7982.500000000', expected '7982.500000000', error '0.000000000'
16
Input
200 15000 84 83 73275 131 51 64307 20 199 81605 142 173 60661 30 147 13009 177 37 25243 147 33 47583 35 3 42773 185 38 6551 175 133 32913 99 142 66370 148 9 91817 129 182 72326 60 25 7372 200 156 40636 106 84 14887 47 83 30863 63 161 603...
Participant's output
5128.00000000000
Jury's answer
5128.00
Checker comment
ok found '5128.000000000', expected '5128.000000000', error '0.000000000'
17
Input
200 19000 17 171 21012 49 73 81438 117 183 46686 183 37 90676 96 143 48334 11 163 62136 199 76 10355 21 24 86173 193 182 96137 40 153 50877 106 85 41879 55 127 60908 51 96 54674 140 69 34889 52 178 69695 90 141 53489 128 124 71734 78 158...
Participant's output
4567.00000000000
Jury's answer
4567.00
Checker comment
ok found '4567.000000000', expected '4567.000000000', error '0.000000000'
18
Input
200 19900 178 113 1777 48 91 98240 93 173 46835 52 175 26256 163 187 60754 190 59 17320 30 63 45470 119 37 87259 161 56 94552 144 107 97547 166 79 91290 166 129 35046 180 59 70820 9 51 50783 143 5 66660 145 184 13929 102 30 88097 43 97 1...
Participant's output
4420.00000000000
Jury's answer
4420.00
Checker comment
ok found '4420.000000000', expected '4420.000000000', error '0.000000000'
19
Input
50 500 25 6 60606 3 7 1111 34 23 39088 13 5 93913 22 6 58355 49 47 37047 47 5 34167 46 9 89752 11 37 82809 19 14 31593 2 7 29436 49 14 52062 34 37 79193 4 37 23637 10 12 39789 40 12 86139 30 32 53841 44 28 25832 25 37 42279 45 46 93638...
Participant's output
28355.50000000000
Jury's answer
28355.50
Checker comment
ok found '28355.500000000', expected '28355.500000000', error '0.000000000'
20
Input
100 3000 40 31 92222 25 54 42654 85 69 9406 56 66 5410 13 26 15452 68 19 21425 17 68 10542 52 82 60093 61 27 64268 94 46 87045 40 43 87541 30 22 60399 22 77 68878 54 14 56724 52 9 17674 11 26 85076 57 80 68486 55 13 92875 44 73 88491 6...
Participant's output
11209.50000000000
Jury's answer
11209.50
Checker comment
ok found '11209.500000000', expected '11209.500000000', error '0.000000000'
21
Input
50 1225 38 24 499 20 9 859 39 43 549 45 41 807 38 2 379 18 10 298 35 33 1285 1 25 699 13 20 649 38 46 780 8 11 696 28 9 983 8 34 671 41 36 473 36 14 573 47 25 1362 40 1 577 18 27 473 42 32 809 7 14 869 26 30 701 13 17 986 1 33 872 ...
Participant's output
1004.50000000000
Jury's answer
1004.50
Checker comment
ok found '1004.500000000', expected '1004.500000000', error '0.000000000'
22
Input
100 4950 28 34 429 75 89 434 60 74 362 100 3 314 49 47 337 12 70 197 24 1 205 20 33 120 65 22 399 49 5 495 59 6 162 49 39 368 15 29 375 40 55 221 64 39 232 26 45 315 73 92 230 43 91 391 67 27 403 85 74 297 37 70 182 80 99 345 90 47 ...
Participant's output
443.00000000000
Jury's answer
443.00
Checker comment
ok found '443.000000000', expected '443.000000000', error '0.000000000'
23
Input
200 19900 73 78 207 149 32 203 93 121 243 136 70 165 79 149 214 173 7 201 14 200 143 69 138 201 149 191 127 168 80 280 150 44 259 24 164 229 152 78 221 30 185 92 171 115 275 147 65 243 63 147 260 91 99 16 34 83 224 80 151 232 83 41 23...
Participant's output
237.00000000000
Jury's answer
237.00
Checker comment
ok found '237.000000000', expected '237.000000000', error '0.000000000'
24
Input
200 19900 133 45 26 64 94 48 189 181 42 178 191 19 115 48 27 25 75 46 154 197 26 173 70 31 45 78 29 162 24 37 85 69 46 162 61 30 20 183 52 95 123 38 88 58 18 85 33 31 76 96 55 45 180 61 193 145 25 117 148 45 117 70 48 92 36 41 88 84...
Participant's output
44.00000000000
Jury's answer
44.00
Checker comment
ok found '44.000000000', expected '44.000000000', error '0.000000000'
25
Input
200 19900 168 63 46 66 137 42 82 169 46 61 70 14 47 5 60 179 166 40 34 122 35 110 15 57 112 128 38 164 61 36 174 31 42 101 21 44 137 186 57 125 196 9 130 184 42 24 42 46 140 45 49 103 69 41 192 60 48 65 117 30 33 124 22 117 187 44 6...
Participant's output
67.50000000000
Jury's answer
67.50
Checker comment
ok found '67.500000000', expected '67.500000000', error '0.000000000'
26
Input
200 19900 141 126 148 102 126 107 124 95 160 55 14 152 77 148 66 171 145 255 74 73 213 102 68 166 178 71 157 110 71 183 146 142 213 18 118 245 41 130 275 150 19 193 39 65 64 188 43 201 185 29 164 65 9 149 36 65 121 185 129 131 154 29 ...
Participant's output
263.50000000000
Jury's answer
263.50
Checker comment
ok found '263.500000000', expected '263.500000000', error '0.000000000'
27
Input
200 19900 2 1 100000 3 1 100000 3 2 100000 4 1 100000 4 2 100000 4 3 100000 5 1 100000 5 2 100000 5 3 100000 5 4 100000 6 1 100000 6 2 100000 6 3 100000 6 4 100000 6 5 100000 7 1 100000 7 2 100000 7 3 100000 7 4 100000 7 5 100000 7 6 ...
Participant's output
100000.00000000000
Jury's answer
100000.00
Checker comment
ok found '100000.000000000', expected '100000.000000000', error '0.000000000'
28
Input
200 19900 2 1 1 3 1 1 3 2 1 4 1 1 4 2 1 4 3 1 5 1 1 5 2 1 5 3 1 5 4 1 6 1 1 6 2 1 6 3 1 6 4 1 6 5 1 7 1 1 7 2 1 7 3 1 7 4 1 7 5 1 7 6 1 8 1 1 8 2 1 8 3 1 8 4 1 8 5 1 8 6 1 8 7 1 9 1 1 9 2 1 9 3 1 9 4 1 9 5 1 9 6 1 9 7 1 ...
Participant's output
1.00000000000
Jury's answer
1.00
Checker comment
ok found '1.000000000', expected '1.000000000', error '0.000000000'
29
Input
200 19900 119 11 141 174 137 71 70 113 117 95 80 323 141 82 179 71 153 115 198 8 112 41 160 108 122 150 27 118 5 92 81 83 57 115 80 276 175 93 108 130 7 99 42 32 174 90 55 78 138 159 26 60 157 128 193 52 90 82 54 188 1 61 125 6 1 102...
Participant's output
175.00000000000
Jury's answer
175.00
Checker comment
ok found '175.000000000', expected '175.000000000', error '0.000000000'
30
Input
200 19900 2 1 92357 3 1 92357 3 2 92357 4 1 92357 4 2 92357 4 3 92357 5 1 92357 5 2 92357 5 3 92357 5 4 92357 6 1 92357 6 2 92357 6 3 92357 6 4 92357 6 5 92357 7 1 92357 7 2 92357 7 3 92357 7 4 92357 7 5 92357 7 6 92357 8 1 92357 8 ...
Participant's output
92357.00000000000
Jury's answer
92357.00
Checker comment
ok found '92357.000000000', expected '92357.000000000', error '0.000000000'
31
Input
200 199 180 159 15362 27 183 93499 38 146 22939 118 72 48743 21 75 67187 170 178 33236 79 157 6244 100 160 63878 185 21 81832 185 177 99279 5 101 29829 130 52 32247 64 33 69155 96 118 85020 133 2 27999 105 82 7826 39 149 83000 132 180 45...
Participant's output
482493.00000000000
Jury's answer
482493.00
Checker comment
ok found '482493.000000000', expected '482493.000000000', error '0.000000000'
32
Input
200 200 20 183 51618 194 153 80810 110 189 88681 150 84 92505 142 26 61434 131 163 70843 168 139 20146 167 171 25126 148 118 82742 140 2 65690 130 72 51429 36 120 2471 51 148 91749 105 110 79500 1 89 29471 138 188 29114 133 148 65863 28 ...
Participant's output
417301.00000000000
Jury's answer
417301.00
Checker comment
ok found '417301.000000000', expected '417301.000000000', error '0.000000000'
33
Input
200 201 91 149 54221 79 179 24392 27 141 9808 129 29 46566 87 180 38069 148 35 15093 60 115 67447 162 51 87940 187 87 87564 180 33 52340 138 194 96478 176 144 12237 39 117 83508 55 117 41995 57 4 27663 18 2 39509 139 142 29200 66 144 141...
Participant's output
412234.00000000000
Jury's answer
412234.00
Checker comment
ok found '412234.000000000', expected '412234.000000000', error '0.000000000'
34
Input
200 19900 56 88 73667 32 189 37556 126 97 31492 135 194 77226 46 165 55957 123 62 92510 150 138 12212 170 180 48729 76 141 64995 58 89 72247 186 199 37516 23 22 86166 97 99 98654 103 138 26314 137 101 55094 70 64 35181 46 171 15257 199 1...
Participant's output
4120.50000000000
Jury's answer
4120.50
Checker comment
ok found '4120.500000000', expected '4120.500000000', error '0.000000000'
35
Input
200 19900 61 70 80666 55 191 42630 118 163 32352 46 198 35858 157 115 10613 170 7 42906 145 52 66655 70 122 47602 3 57 6537 162 89 19500 80 154 46528 51 46 37703 182 195 85934 95 40 59126 118 186 82064 10 57 44488 96 171 94550 131 114 57...
Participant's output
4266.50000000000
Jury's answer
4266.50
Checker comment
ok found '4266.500000000', expected '4266.500000000', error '0.000000000'
36
Input
50 500 7 5 55101 47 49 61815 13 34 76862 48 16 54805 11 27 52647 18 35 56570 37 36 90568 10 12 63442 36 41 45476 22 3 79709 13 18 43041 9 35 69227 7 42 67400 7 49 34230 43 25 5817 18 2 30876 15 42 84879 27 15 93784 35 38 67915 10 22 93...
Participant's output
29447.00000000000
Jury's answer
29203.00
Checker comment
wrong answer 1st numbers differ - expected: '29203.0000000', found: '29447.0000000', error = '0.0083553'