QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#188484	#6845. Tax	rsj	WA	227ms	3520kb	C++14	1.3kb	2023-09-25 21:24:47	2023-09-25 21:24:47

Judging History

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

[2023-09-25 21:24:47]
评测

测评结果：WA
用时：227ms
内存：3520kb

查看

[2023-09-25 21:24:47]
提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
#define int long long

int a[N*N];
struct edge {
	int to,w;
	edge *nex;
}*head[N];
void add(int u,int v,int w) {
	edge *cur=new edge;
	cur->to=v;
	cur->w=w;
	cur->nex=head[u];
	head[u]=cur;
}
int vis[N],dis[N];
void spfa(int u) {
	queue<int> q;
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	dis[u]=0;
	q.push(u);
	vis[u]=1;
	while(!q.empty()) {
		u=q.front(); q.pop(); vis[u]=0;
		for(edge *cur=head[u];cur;cur=cur->nex) {
			if(dis[cur->to]>dis[u]+1) {
				dis[cur->to]=dis[u]+1;
				if(!vis[cur->to]) {
					vis[cur->to]=1;
					q.push(cur->to);
				}
			}
		}
	}
}

int n,m;

int cnt[N],ans;
int Ans[N];
int cal(int x) {
	return cnt[x]*(cnt[x]+1)/2*a[x];
}

void dfs(int u) {
	Ans[u]=min(Ans[u],ans);
	for(edge *cur=head[u];cur;cur=cur->nex) {
		if(dis[cur->to]!=dis[u]+1) continue;
		
		ans-=cal(cur->w);
		cnt[cur->w]++;
		ans+=cal(cur->w);
		dfs(cur->to);
		ans-=cal(cur->w);
		cnt[cur->w]--;
		ans+=cal(cur->w);
	}
}

signed main() {
	memset(Ans,0x3f,sizeof(Ans));
	int i,u,v,w,j;
	cin>>n>>m;
	for(i=1;i<=m;i++) cin>>a[i];
	for(i=1;i<=m;i++) {
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	spfa(1);
	dfs(1);
	for(i=2;i<=n;i++) cout<<Ans[i]<<endl;
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3408kb

input:

5 6
1 8 2 1 3 9
1 2 1
2 3 2
1 4 1
3 4 6
3 5 4
4 5 1

output:

result:

ok 4 lines

Test #2:

score: 0

Accepted

time: 0ms

memory: 3520kb

input:

10 15
730 2163 6818 4647 9699 1037 2034 8441 2619 6164 464 4369 4500 6675 1641
1 6 2
3 6 1
3 2 1
9 2 2
7 3 1
6 5 1
5 3 2
3 10 1
10 2 2
5 10 1
8 2 2
9 8 1
7 4 2
4 5 2
4 10 2

output:

result:

ok 9 lines

Test #3:

score: 0

Accepted

time: 1ms

memory: 3468kb

input:

10 15
847 2302 8846 8055 585 6541 6493 7165 5376 8551 836 2993 2700 9323 5119
2 1 5
2 3 3
3 10 3
10 4 3
8 3 4
10 8 1
3 7 3
4 5 3
5 8 5
6 3 3
8 6 2
6 5 4
9 10 2
7 9 4
5 9 4

output:

result:

ok 9 lines

Test #4:

score: 0

Accepted

time: 1ms

memory: 3452kb

input:

20 30
4547 9278 5093 443 7292 7570 7138 9315 4114 723 9854 9584 294 1861 5478 2734 5967 7102 6137 9504 456 7980 9645 6571 336 5308 1035 8008 3128 4035
7 1 2
11 7 1
11 12 2
12 10 2
10 5 2
20 5 1
20 17 2
17 16 2
16 18 1
7 19 3
19 12 1
2 18 2
3 7 1
12 3 1
19 3 1
13 11 1
12 13 1
19 13 1
13 3 2
18 15 2
8...

output:

result:

ok 19 lines

Test #5:

score: 0

Accepted

time: 0ms

memory: 3488kb

input:

20 30
2477 6652 1326 9801 9300 5132 8051 7482 5793 1154 4960 1452 2591 6386 6573 9726 7902 868 9089 6179 7249 2439 5355 8561 7168 3785 9180 2898 8103 5168
10 1 2
10 15 5
15 2 3
2 5 1
6 5 5
9 6 3
9 18 2
20 18 1
20 14 3
8 2 5
13 10 3
13 2 1
5 19 1
9 19 4
19 8 3
9 12 1
19 12 4
7 15 5
7 2 4
16 10 2
16 1...

output:

result:

ok 19 lines

Test #6:

score: 0

Accepted

time: 1ms

memory: 3400kb

input:

20 30
3440 3226 6455 7629 6160 9354 1868 2631 4819 1142 7323 8166 4862 9851 7430 8785 3563 7421 2271 9637 6088 2754 4062 8932 7510 7797 9647 8657 4123 293
9 1 18
9 4 17
4 14 7
14 17 7
7 17 14
3 7 13
3 10 11
10 16 16
16 13 6
9 20 20
20 4 13
10 8 3
13 8 16
4 5 20
11 16 11
8 11 13
2 17 12
4 18 1
18 17 ...

output:

result:

ok 19 lines

Test #7:

score: 0

Accepted

time: 0ms

memory: 3384kb

input:

30 50
7129 2843 1688 6915 6827 4756 6845 140 1403 8426 6939 8317 2320 9371 1611 8403 8356 3846 7594 9874 6888 5183 7945 6815 2910 3776 1550 2580 5566 5155 3505 1935 945 4665 3328 4162 9529 6486 7771 8357 471 354 7208 3344 8628 7321 4624 9058 3737 6828
1 10 3
10 17 1
17 5 1
21 5 1
21 9 3
30 9 3
30 8 ...

output:

result:

ok 29 lines

Test #8:

score: 0

Accepted

time: 0ms

memory: 3488kb

input:

30 50
1816 811 3173 8236 9775 9764 9318 2725 3832 2365 5954 6959 72 3542 3353 6839 5277 3333 9313 3833 8198 1409 1669 7304 1094 5752 7393 9532 8997 6858 728 5391 1567 5803 2319 5231 8563 9045 1695 928 6021 4868 6246 1639 3132 6408 5335 1263 6884 6134
17 1 8
17 10 7
10 28 4
3 28 6
3 7 9
7 22 6
25 22 ...

output:

result:

ok 29 lines

Test #9:

score: 0

Accepted

time: 1ms

memory: 3456kb

input:

30 50
9227 712 7087 3799 7334 2513 2685 8147 5727 415 5898 8487 1938 9946 6164 46 7086 5664 318 3545 840 7810 6397 4201 6297 6036 9036 3750 5708 3216 7705 8875 17 3620 1046 6055 6077 3839 4393 605 9048 6984 1692 6869 317 5863 3725 3897 1213 9498
23 1 5
29 23 1
30 29 14
24 30 19
24 14 15
14 16 15
16 ...

output:

result:

ok 29 lines

Test #10:

score: 0

Accepted

time: 1ms

memory: 3484kb

input:

30 50
5448 5807 3224 8952 8304 8530 5876 727 784 1901 7392 2903 8670 6927 1771 2274 4866 9258 794 9474 7772 5238 8948 2154 3691 4109 917 6173 1719 7485 3788 9957 8904 9705 6252 1773 8092 4024 8863 8888 5061 2373 9550 184 4905 4045 3114 6519 4400 9876
1 2 11
9 2 17
9 24 7
24 5 24
12 5 34
29 12 5
29 4...

output:

result:

ok 29 lines

Test #11:

score: 0

Accepted

time: 1ms

memory: 3448kb

input:

40 50
7141 3687 8409 3882 3187 6878 5145 491 1769 4034 9678 9137 7998 9960 9383 604 7306 4107 535 4895 4170 1927 1124 3027 573 7950 8425 3602 1129 4551 676 7260 6102 4234 3720 357 5633 9349 5676 7845 7755 7386 7851 1015 9880 8110 7090 3914 7073 92
26 1 2
5 26 2
30 5 1
14 30 2
12 5 1
12 39 1
30 3 2
1...

output:

result:

ok 39 lines

Test #12:

score: 0

Accepted

time: 1ms

memory: 3420kb

input:

40 50
3550 4246 2743 1166 9068 9921 4276 9903 3846 3706 3231 6720 950 9253 8797 8222 3242 3654 1910 2491 9491 9689 5203 570 7111 4413 2374 997 160 8611 258 3447 1883 1188 351 2995 666 4569 4168 7563 1506 5825 220 825 382 8350 7040 3417 9226 4408
1 37 1
37 15 4
15 35 3
2 35 4
11 15 3
2 12 4
4 1 1
33 ...

output:

result:

ok 39 lines

Test #13:

score: 0

Accepted

time: 0ms

memory: 3448kb

input:

40 50
6324 7516 8231 869 6928 3161 8484 8886 6656 4740 6205 6425 3058 6571 522 1895 7751 2720 6454 4651 7779 9785 3599 1620 383 3999 8983 1287 6583 4399 8501 9660 6221 6988 5925 3500 1876 1883 9716 953 8693 1749 5461 7958 7229 1320 9710 8219 6381 5367
1 30 9
27 30 13
24 27 6
24 37 3
27 29 9
12 27 5
...

output:

result:

ok 39 lines

Test #14:

score: 0

Accepted

time: 1ms

memory: 3496kb

input:

40 50
3155 2853 7048 6482 5037 1695 4171 9685 1590 579 8293 3794 8226 445 708 6304 7865 3502 9897 3416 4232 315 3994 6201 4732 6220 1025 1255 6170 190 6475 5592 3962 2594 9801 3734 5095 9100 5874 6623 4224 2756 2879 3112 555 5640 3886 3542 1661 5384
1 11 25
11 31 3
31 4 40
14 4 8
4 28 35
38 14 5
38 ...

output:

result:

ok 39 lines

Test #15:

score: 0

Accepted

time: 0ms

memory: 3488kb

input:

50 100
9400 6363 1176 8951 4801 3283 7949 4588 1161 6901 8301 7311 1900 7944 3213 1057 5241 2819 4614 9730 2052 5218 9622 7594 6740 2968 2144 6132 1766 6151 7031 8157 7480 825 9559 8985 5039 4155 5133 4143 5650 1517 6953 1960 3116 899 4835 484 9182 5271 1172 5332 1514 7540 5448 3025 1785 9324 2275 5...

output:

result:

ok 49 lines

Test #16:

score: 0

Accepted

time: 1ms

memory: 3424kb

input:

50 100
8240 7415 7952 6913 9892 3649 6284 2996 7935 1716 7358 7425 8728 1747 4736 480 9949 8266 816 1739 3212 6436 273 3122 7882 1666 6009 5831 2560 4923 6401 515 5752 1062 1544 2063 5156 993 385 5212 7896 1006 8032 3851 2075 5073 896 4582 4522 6771 9856 1685 1221 7746 1745 5018 9840 4254 5450 1910 ...

output:

result:

ok 49 lines

Test #17:

score: 0

Accepted

time: 1ms

memory: 3448kb

input:

50 85
2999 6976 3472 6677 8361 8394 8333 3013 9489 4970 9434 6093 1299 969 5194 2383 907 1393 5041 5599 4184 2498 7974 1640 2604 7280 6040 231 6862 3730 678 2526 8887 6389 8678 5587 7368 9000 7967 4718 9571 2446 286 7679 5310 1487 9413 4309 9684 4742 9367 8520 9459 1604 8670 224 9966 9708 6886 3819 ...

output:

result:

ok 49 lines

Test #18:

score: 0

Accepted

time: 0ms

memory: 3488kb

input:

50 49
4809 6241 6063 3007 5326 2587 2620 9604 4597 8453 3771 6578 7057 3741 1385 6718 6331 4914 2120 4963 9007 2953 4590 4928 4875 8347 9123 4712 8051 8324 7 4977 2448 70 6921 4774 6476 2212 2625 5477 5063 199 7959 6498 5173 9741 4281 9938 5086
1 25 33
25 13 21
43 13 18
31 43 37
31 32 8
32 19 30
19 ...

output:

result:

ok 49 lines

Test #19:

score: 0

Accepted

time: 227ms

memory: 3460kb

input:

50 269
8772 4767 6243 8961 1273 343 7907 6384 6219 4524 330 2426 8970 302 6975 3672 8151 3601 8863 2951 9897 8108 3804 522 6731 9386 3833 869 6172 4107 8368 7124 8941 5412 9468 9794 1431 4267 8959 8850 3010 6444 429 1066 6863 7815 9407 4851 9776 4351 7570 7147 9338 540 5957 4722 4986 9450 3358 9600 ...

output:

result:

ok 49 lines

Test #20:

score: 0

Accepted

time: 199ms

memory: 3408kb

input:

50 256
3851 484 7665 9522 7179 9670 4086 4079 7462 1907 1291 5302 817 879 4620 9239 6901 8916 8606 9191 3725 7777 3095 3164 2314 5159 3857 2258 4066 2107 2619 777 3389 4232 4695 4548 1927 7114 6237 3147 7409 5971 23 5930 3536 2969 307 3264 7917 7542 4997 5089 9827 2551 5250 8517 1235 2174 965 7846 1...

output:

result:

ok 49 lines

Test #21:

score: 0

Accepted

time: 10ms

memory: 3516kb

input:

50 400
4854 3873 6490 2864 7115 4132 4115 2742 2420 5025 9948 409 5130 8776 6673 265 5562 4057 1487 3019 7174 6220 9483 7494 4642 8377 6491 5080 3655 4160 4890 7919 4290 4931 3432 1697 6854 1911 8744 6196 4790 9383 3537 2086 2044 1025 1406 982 6693 2598 7310 9289 1379 1950 916 7894 2010 7186 8168 45...

output:

result:

ok 49 lines

Test #22:

score: -100

Wrong Answer

time: 27ms

memory: 3504kb

input:

50 363
2223 9955 5736 1379 3130 2969 5992 8338 3871 7470 8953 6368 5152 5993 3889 7829 7698 9459 1125 6539 606 1132 5282 9348 2976 1060 3381 131 5803 946 9459 1441 740 913 8866 5962 7443 8014 1022 1758 277 1531 3445 7664 988 5152 9163 8234 5133 6772 7031 3863 7905 9048 8996 9832 9909 285 6545 2848 9...

output:

result:

wrong answer 4th lines differ - expected: '32602', found: '38756'