QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #705102 | #518. Tours de Sales Force | TheZone | AC ✓ | 12819ms | 536412kb | C++14 | 4.4kb | 2024-11-02 22:09:29 | 2024-11-02 22:09:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const double inf = 1e9;
double dp[17][1 << 16];
double res[25][25];
double di[16][16];
double ndp[2][1 << 25];
double dist(pi a, pi b){
return sqrtl((a.fi - b.fi) * (a.fi - b.fi) + (a.se - b.se) * (a.se - b.se));
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<vector<pi>> p(n);
for(int i = 0; i < n; i++){
int d;
cin >> d;
for(int j = 0; j < d; j++){
int x, y;
cin >> x >> y;
p[i].pb({x, y});
}
}
double ans0 = 0.0;
for(int i = 0; i < n; i++){
int s = (int)(p[i].size());
for(int k = 0; k < (1 << s); k++) for(int l = 0; l < s; l++) dp[l][k] = inf;
for(int k = 0; k < s; k++){
for(int a = 0; a < s; a++){
di[k][a] = dist(p[i][k], p[i][a]);
}
}
dp[0][1] = 0.0;
for(int k = 0; k < (1 << s); k++){
for(int a = 0; a < s; a++) if(dp[a][k] != inf){
for(int l = 0; l < s; l++) if(!(k & (1 << l))){
dp[l][k | (1 << l)] = min(dp[l][k | (1 << l)], dp[a][k] + di[a][l]);
}
}
}
double cur = inf;
for(int k = 0; k < s; k++) cur = min(cur, dp[k][(1 << s) - 1] + dist(p[i][k], p[i][0]));
ans0 += cur;
}
cout << fixed << setprecision(10) << ans0 << ' ';
for(int i = 0; i < n / 2; i++) for(int j = n / 2; j < n; j++){
vector<pi> q;
for(pi x : p[i]) q.pb(x);
for(pi x : p[j]) q.pb(x);
int s = (int)(q.size());
for(int k = 0; k < (1 << s); k++) for(int l = 0; l < s; l++) dp[l][k] = inf;
dp[0][1] = 0.0;
for(int k = 0; k < s; k++){
for(int a = 0; a < s; a++){
di[k][a] = dist(q[k], q[a]);
}
}
for(int k = 0; k < (1 << s); k++){
for(int a = 0; a < s; a++) if(dp[a][k] != inf){
for(int l = 0; l < s; l++) if(!(k & (1 << l))){
dp[l][k | (1 << l)] = min(dp[l][k | (1 << l)], dp[a][k] + di[a][l]);
}
}
}
res[i][j - n / 2] = inf;
for(int k = 0; k < s; k++) res[i][j - n / 2] = min(res[i][j - n / 2], dp[k][(1 << s) - 1] + di[k][0]);
}
for(int i = 0; i < 2; i++) for(int j = 0; j < (1 << (n / 2)); j++) ndp[i][j] = inf;
ndp[0][0] = 0;
for(int i = 0; i < n / 2; i++){
int cr = i & 1;
int nxt = 1 - cr;
for(int j = 0; j < (1 << (n / 2)); j++) if(ndp[cr][j] != inf){
for(int l = 0; l < n / 2; l++) if(!(j & (1 << l))){
ndp[nxt][j | (1 << l)] = min(ndp[nxt][j | (1 << l)], ndp[cr][j] + res[i][l]);
}
}
for(int j = 0; j < (1 << (n / 2)); j++) ndp[cr][j] = inf;
}
cout << fixed << setprecision(10) << ndp[(n / 2) & 1][(1 << (n / 2)) - 1] << '\n';
return 0;
}
/*#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const double inf = 1e9;
double dp[17][1 << 16];
double res[25][25];
double di[16][16];
double ndp[2][1 << 25];
double dist(pi a, pi b){
return sqrtl((a.fi - b.fi) * (a.fi - b.fi) + (a.se - b.se) * (a.se - b.se));
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<vector<pi>> p(n);
for(int i = 0; i < n; i++){
int d;
cin >> d;
for(int j = 0; j < d; j++){
int x, y;
cin >> x >> y;
p[i].pb({x, y});
}
}
double ans0 = 0.0;
for(int i = 0; i < n; i++){
int s = (int)(p[i].size());
for(int k = 0; k < (1 << s); k++) for(int l = 0; l < s; l++) dp[l][k] = inf;
for(int k = 0; k < s; k++){
for(int a = 0; a < s; a++){
di[k][a] = dist(p[i][k], p[i][a]);
}
}
dp[0][1] = 0.0;
for(int k = 0; k < (1 << s); k++){
for(int a = 0; a < s; a++) if(dp[a][k] != inf){
for(int l = 0; l < s; l++) if(!(k & (1 << l))){
dp[l][k | (1 << l)] = min(dp[l][k | (1 << l)], dp[a][k] + di[a][l]);
}
}
}
double cur = inf;
for(int k = 0; k < s; k++) cur = min(cur, dp[k][(1 << s) - 1] + dist(p[i][k], p[i][0]));
ans0 += cur;
}
cout << fixed << setprecision(10) << ans0 << ' ';
for(int i = 0; i < n / 2; i++) for(int j = n / 2; j < n; j++){
vector<pi> q;
for(pi x : p[i]) q.pb(x);
for(pi x : p[j]) q.pb(x);
int s = (int)(q.size());
for(int k = 0; k < (1 << s); k++) for(int l = 0; l < s; l++) dp[l][k] = inf;
dp[0][1] = 0.0;
for(int k = 0; k < s; k++){
}
for(int j = 0; j < (1 << (n / 2)); j++) ndp[cr][j] = inf;
}
cout << fixed << setprecision(10) << ndp[(n / 2) & 1][(1 << (n / 2)) - 1] << '\n';
return 0;*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 12100kb
input:
4 6 0 10 0 20 5 30 10 20 10 10 5 0 4 40 20 40 30 50 20 50 30 4 20 10 30 20 20 20 30 10 3 55 10 45 10 50 0
output:
177.0820393250 179.4427191000
result:
ok 2 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 10044kb
input:
2 3 0 0 100 100 100 -100 3 200 100 300 0 200 -100
output:
965.6854249492 765.6854249492
result:
ok 2 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 9996kb
input:
2 3 -10000 -10000 -10000 10000 10000 -10000 3 10000 10000 10000 9999 9999 10000
output:
68287.6854610243 80000.0000000000
result:
ok 2 numbers
Test #4:
score: 0
Accepted
time: 12819ms
memory: 536412kb
input:
50 8 19 55 34 49 26 72 98 42 22 31 36 34 8 31 10 82 8 135 18 104 28 106 84 152 15 145 79 107 0 157 89 191 41 8 289 0 218 61 295 19 266 43 282 50 241 60 213 92 288 51 8 387 86 362 36 329 87 338 73 309 74 396 98 340 28 367 79 8 82 111 61 174 84 161 83 191 27 141 53 120 20 195 40 193 8 127 110 148 188 ...
output:
12979.5860515929 38557.7594507345
result:
ok 2 numbers
Test #5:
score: 0
Accepted
time: 12767ms
memory: 536412kb
input:
50 8 35 35 25 64 97 3 45 85 13 77 34 94 75 78 95 88 8 137 19 113 42 148 40 199 77 155 62 153 18 182 65 189 10 8 236 86 222 12 223 62 255 22 220 39 292 87 234 47 203 61 8 340 42 398 11 359 7 310 17 324 65 367 6 306 0 351 86 8 82 195 37 168 52 139 78 194 61 166 65 184 77 125 38 117 8 159 118 112 100 1...
output:
13148.8731348882 39065.1058378723
result:
ok 2 numbers
Test #6:
score: 0
Accepted
time: 2ms
memory: 12032kb
input:
4 4 0 0 0 10 10 0 10 10 4 50 250 60 260 50 260 60 250 4 20 0 20 10 30 10 30 0 4 50 -250 60 -260 60 -250 50 -260
output:
160.0000000000 1113.6374162572
result:
ok 2 numbers
Test #7:
score: 0
Accepted
time: 17ms
memory: 14240kb
input:
2 8 -515 857 588 -809 -719 695 391 -921 87 996 -469 883 -208 -978 -809 -588 8 -144 -139 164 115 171 -103 -160 120 -166 -112 112 166 35 197 -14 200
output:
6758.3490272468 6342.0880303307
result:
ok 2 numbers
Test #8:
score: 0
Accepted
time: 13ms
memory: 15444kb
input:
2 8 -144 -139 164 115 171 -103 -160 120 -166 -112 112 166 35 197 -14 200 8 -515 857 588 -809 -719 695 391 -921 87 996 -469 883 -208 -978 -809 -588
output:
6758.3490272468 6342.0880303307
result:
ok 2 numbers
Test #9:
score: 0
Accepted
time: 0ms
memory: 12116kb
input:
6 4 0 0 30 30 0 30 30 0 4 40 40 70 70 40 70 70 40 4 80 80 110 110 80 110 110 80 4 100 100 130 130 100 130 130 100 4 60 60 90 90 60 90 90 60 4 20 20 50 50 20 50 50 20
output:
720.0000000000 621.4432992636
result:
ok 2 numbers
Test #10:
score: 0
Accepted
time: 1ms
memory: 12004kb
input:
6 4 80 80 110 110 80 110 110 80 4 100 100 130 130 100 130 130 100 4 60 60 90 90 60 90 90 60 4 20 20 50 50 20 50 50 20 4 0 0 30 30 0 30 30 0 4 40 40 70 70 40 70 70 40
output:
720.0000000000 921.8376618407
result:
ok 2 numbers
Test #11:
score: 0
Accepted
time: 1ms
memory: 12108kb
input:
2 4 0 7 7 0 14 7 7 14 4 4 4 4 10 10 4 10 10
output:
63.5979797464 40.0000000000
result:
ok 2 numbers
Test #12:
score: 0
Accepted
time: 944ms
memory: 16120kb
input:
16 8 66 75 73 50 73 66 74 35 10 11 82 60 59 42 2 14 8 192 72 166 44 118 27 153 21 125 30 147 65 197 67 149 79 8 216 99 259 89 248 97 218 53 220 79 205 70 271 65 213 58 8 393 76 340 43 333 46 330 15 327 3 345 1 375 96 319 72 8 62 161 53 114 82 128 95 157 88 195 69 101 85 182 0 130 8 177 138 120 199 1...
output:
4072.7314867673 5516.1718378470
result:
ok 2 numbers
Test #13:
score: 0
Accepted
time: 199ms
memory: 14168kb
input:
16 7 60 19 24 30 19 46 17 61 2 9 24 28 31 52 7 106 91 191 11 164 8 106 32 115 77 176 12 185 19 7 225 47 208 11 263 13 237 49 267 96 284 92 260 48 7 386 77 382 93 307 75 311 84 341 74 398 21 309 83 7 9 167 20 112 45 172 13 152 11 147 44 121 62 190 7 158 100 114 181 188 125 142 104 157 136 129 153 136...
output:
3845.0812642147 5385.7571174852
result:
ok 2 numbers
Test #14:
score: 0
Accepted
time: 306ms
memory: 16136kb
input:
32 5 -532 2643 -2871 -5782 2064 -8512 2161 449 -2723 -7391 5 -3117 -2567 7955 -6983 -8293 8040 1206 4984 -6534 -592 3 8934 6580 -3687 138 -4383 -2757 3 -1922 -2021 -7285 597 -7464 -9220 7 -8681 6736 -2966 -9468 -7155 -63 -4216 -3946 -3372 -5609 -5090 -825 -5364 4427 3 -3778 979 -83 208 -672 -7891 4 ...
output:
1222823.6432875481 762250.5100895572
result:
ok 2 numbers
Test #15:
score: 0
Accepted
time: 115ms
memory: 16340kb
input:
28 4 -9516 -8112 3167 -6150 -2375 -3147 6416 2477 6 -7171 -1763 1311 -9911 -3659 -3965 -1704 -2807 7758 -3474 5335 8946 4 -3588 -3663 -8215 -3021 -7187 864 -4232 5457 5 -9762 -9057 -1319 1058 1742 1447 -898 -7113 9660 8344 3 -8298 -5244 -8725 -4304 -22 954 8 -4372 9237 -5824 -8009 5967 2182 -7844 70...
output:
1089249.0896978523 679061.2053932144
result:
ok 2 numbers
Test #16:
score: 0
Accepted
time: 541ms
memory: 20324kb
input:
36 3 -8692 -1458 1343 -7137 -5804 838 4 -3201 -3907 -7039 -882 -1819 -8871 -4414 -9048 4 2685 -7205 -1996 -991 1221 -6238 -5314 -3254 4 871 -9976 -3516 -7997 3332 -8878 1860 -8635 3 -5541 -9984 -4817 -6584 -9601 -5078 5 1208 2700 -235 64 -8968 -3535 3128 6910 -9652 4851 7 -1061 9597 -8634 -147 -2916...
output:
1413114.5005563023 898602.4099624295
result:
ok 2 numbers
Test #17:
score: 0
Accepted
time: 188ms
memory: 15480kb
input:
30 6 -3697 -7610 -5954 7216 -1223 -1522 -8054 8560 -5681 -6510 2641 129 5 -5732 5089 -237 -8115 180 3918 8173 4792 -366 6082 6 -3500 1971 -1132 -8273 -4753 -5171 -5546 -4424 -5249 -1185 -873 -9649 8 -9331 448 1506 2072 -502 -544 5331 2450 5144 -4819 -8176 -7447 1997 73 8038 -7738 8 -6363 -2127 -8220...
output:
1118954.7503049709 708290.2494684935
result:
ok 2 numbers
Test #18:
score: 0
Accepted
time: 155ms
memory: 14212kb
input:
26 8 -2771 -3509 9833 8570 6645 9130 -9075 -7792 -4498 -6862 9371 -1170 1595 -597 -80 -3800 8 8591 -9103 -4604 -4255 9053 329 8213 9873 1238 -2772 -7513 4007 2342 1311 6432 -3251 4 2682 -794 732 -3244 7083 -2883 -2725 -1773 8 1620 -985 -4264 -6374 -4896 -6954 -3925 847 -2135 -5698 -5564 9713 -2652 -...
output:
1042117.2416486933 646230.1815997678
result:
ok 2 numbers
Test #19:
score: 0
Accepted
time: 632ms
memory: 15440kb
input:
28 4 -9618 -5560 -1677 -8491 -906 -2579 -8564 384 5 -6686 -378 -520 -7941 -9548 -3879 -8402 4563 4385 -8976 8 -9732 4344 -6795 -321 -3197 1604 -8336 -4276 -3990 8586 -8501 -8997 2133 4113 -9096 1162 6 96 3765 -689 9674 2480 2382 3476 -9268 440 -1980 -153 -817 8 4077 -3432 -3101 -724 -4708 7611 2059 ...
output:
1194811.4221433457 748043.3789080255
result:
ok 2 numbers
Test #20:
score: 0
Accepted
time: 338ms
memory: 14848kb
input:
32 5 2224 -9661 2536 -9845 -8774 6770 -7544 -3266 -6273 -6334 6 778 5757 -1915 -5944 7928 -792 -4025 -3189 4561 -685 -5076 -1042 7 3431 2338 6072 -5035 7250 -6161 4644 148 135 -6482 -5418 -459 -9855 -5991 6 3701 1705 3751 9298 7187 1401 9847 -425 3801 -1310 -5043 3303 3 -5141 -3811 -783 -4632 -5732 ...
output:
1335788.0151754818 826539.1272882464
result:
ok 2 numbers