QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#705102#518. Tours de Sales ForceTheZoneAC ✓12819ms536412kbC++144.4kb2024-11-02 22:09:292024-11-02 22:09:30

Judging History

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

  • [2024-11-02 22:09:30]
  • 评测
  • 测评结果：AC
  • 用时：12819ms
  • 内存：536412kb
查看
  • [2024-11-02 22:09:29]
  • 提交

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;*/
源文件, 语言: C++14

详细

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
English 繁體中文 简体中文

服务器时间: 2024-12-04 07:03:34 | 开源项目