QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#386794#6845. TaxSceneTL 0ms3876kbC++142.2kb2024-04-11 20:14:452024-04-11 20:14:45

Judging History

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

  • [2024-04-11 20:14:45]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3876kb
  • [2024-04-11 20:14:45]
  • 提交

answer

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define fo(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define Ts template<typename Ty,typename... Ar>
#define Tp template<typename Ty>
#define ll long long
#define RS register
#define gc getchar
#define pc putchar
#define I inline
using namespace std;
Tp I Ty wmax(Ty a,Ty b){return a>=b? a:b;}
Tp I Ty wmin(Ty a,Ty b){return a<=b? a:b;}
namespace WrongIO
{
	Tp I void read(Ty &x){x=0;Ty opt=1;char c=gc();while(!isdigit(c)&&c!='-')c=gc();if(c=='-')opt=-1,c=gc();while(isdigit(c))x=(x<<3)+(x<<1),x+=c-'0',c=gc();x*=opt;return;}
	Tp I void write(Ty x){short OI_USE[50],OI_top=0;if(x<=0) if(x==0)pc('0');else pc('-'),x*=-1;while(x)OI_USE[++OI_top]=x%10,x/=10;while(OI_top--)pc(OI_USE[OI_top+1]+'0');return;}
    I void writec(char c[]){int len=strlen(c);for(int i=0;i<len;i++)pc(c[i]);}
    I void writes(string s){int len=s.length();for(int i=0;i<len;i++)pc(s[i]);}
    I void readc(char &c,int l,int r){c=gc(); while(c!=EOF&&(c<l||c>r)) c=gc();}
    I void readc(char &c,char val){c=gc();while(c!=EOF&&c!=val) c=gc();}
    I void readc(char val){char c;c=gc();while(c!=EOF&&c!=val) c=gc();}
    I void readls(string &s){char c=gc();while(c!='\n') s.push_back(c),c=gc();}
    Ts I void read(Ty &x,Ar &...y) {read(x),read(y...);}
} using namespace WrongIO;
int n,m;
int w[55];
struct awa{
	int v,cl;
};
vector<awa> vt[55];
int vis[55],ans[55];
int cz[100050],mp[55][55];
queue<int> q;
void dfs(int u,int at)
{
	ans[u]=min(ans[u],at);
	for(awa tp:vt[u])
	{
		int v=tp.v;
		cz[tp.cl]++;
		dfs(v,at+w[tp.cl]*cz[tp.cl]);
		cz[tp.cl]--;
	} return;
}
int main()
{
	read(n,m);
	for(int i=1;i<=m;i++) read(w[i]);
	for(int i=1;i<=m;i++)
	{
		int u,v,w; read(u,v,w);
		vt[u].push_back(awa{v,w});
		vt[v].push_back(awa{u,w});
		mp[u][v]=mp[v][u]=w;
	}
	q.push(1); vis[1]=1;
	while(!q.empty())
	{
		int u=q.front(); q.pop();
		for(awa tp:vt[u])
		{
			int v=tp.v;
			if(vis[v]!=0) continue;
			vis[v]=vis[u]+1; q.push(v);
		}
	}
	memset(ans,0x3f,sizeof(ans));
	for(int i=1;i<=n;i++) vt[i].clear();
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	if(vis[i]+1==vis[j]&&mp[i][j]!=0) vt[i].push_back(awa{j,mp[i][j]});
	dfs(1,0);
	for(int i=2;i<=n;i++) write(ans[i]),pc('\n');
}

詳細信息

Test #1:

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

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:

1
9
1
3

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3636kb

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:

4353
2893
7219
2893
2163
4353
8679
8679
4353

result:

ok 9 lines

Test #3:

score: 0
Accepted
time: 0ms
memory: 3628kb

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:

585
9431
53661
18656
27123
27123
17486
29425
27123

result:

ok 9 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 3644kb

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:

166078
13825
98229
41653
28012
9278
28012
38198
37474
13825
18918
18918
24557
166078
106231
78397
128966
14371
56754

result:

ok 19 lines

Test #5:

score: 0
Accepted
time: 0ms
memory: 3840kb

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:

10455
13107
40665
15409
24709
29256
19755
27361
6652
67805
32208
7978
52074
15952
19956
34510
40665
22407
48096

result:

ok 19 lines

Test #6:

score: 0
Accepted
time: 0ms
memory: 3872kb

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:

23732
30279
10984
15466
17730
25417
44057
7421
37602
53781
24185
52842
12852
20175
46387
15566
14424
12240
17058

result:

ok 19 lines

Test #7:

score: 0
Accepted
time: 0ms
memory: 3876kb

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:

4531
55325
85265
11660
10217
41067
32538
18657
1688
15036
161199
120867
20722
85265
73893
8817
89352
149383
85265
13593
99480
73893
75137
8817
7129
63765
55325
66697
25409

result:

ok 29 lines

Test #8:

score: 0
Accepted
time: 0ms
memory: 3836kb

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:

88680
11738
77782
107316
83230
19402
74150
59701
4643
7008
13961
61202
2365
38986
89353
2725
85975
83011
12489
49926
29166
79838
59386
36261
64375
48304
12879
3832
66652

result:

ok 29 lines

Test #9:

score: 0
Accepted
time: 0ms
memory: 3584kb

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:

58976
54062
20296
55016
25960
15302
55431
36391
48335
33210
58561
15523
21051
65140
19399
72869
25063
46194
29836
70356
18368
7334
14887
33625
1938
39108
23796
4623
14569

result:

ok 29 lines

Test #10:

score: 0
Accepted
time: 0ms
memory: 3568kb

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:

7392
50123
24002
12810
20902
31604
8119
12258
22068
41795
22515
12442
53875
58060
31774
49567
62545
37777
47482
26560
27116
63133
18134
26156
27693
49756
41001
23275
52561

result:

ok 29 lines

Test #11:

score: 0
Accepted
time: 0ms
memory: 3576kb

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:

22122
29263
32484
11061
21423
43545
18202
32484
18202
32484
18202
25110
29263
25110
53907
43545
3687
58293
29263
32484
43545
32484
32484
22122
3687
53907
18202
10828
18202
10828
29263
7141
43545
32484
10828
7141
29263
32484
43545

result:

ok 39 lines

Test #12:

score: 0
Accepted
time: 0ms
memory: 3532kb

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:

9791
14037
3550
7796
15277
8962
11705
17454
2743
7459
13289
7459
11705
4716
14037
7048
9791
6989
24635
4716
16062
11705
18805
17535
11705
4246
11705
17535
20197
6293
8962
11816
17191
7459
20389
3550
12475
11705
21137

result:

ok 39 lines

Test #13:

score: 0
Accepted
time: 0ms
memory: 3616kb

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:

29329
37568
33890
19265
20068
13744
28434
36845
6324
32579
16642
44139
11396
24158
21260
13840
11944
15140
19446
17370
23213
21359
12875
28034
22630
9714
24298
23026
6656
33448
26374
23001
26390
22110
28746
21106
19446
30729
8886

result:

ok 39 lines

Test #14:

score: 0
Accepted
time: 0ms
memory: 3584kb

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:

58203
32436
18403
47766
31819
51728
55992
53329
30047
4732
24604
36914
28088
52354
39901
23440
36069
52861
21244
42887
34027
40083
49088
52803
36667
22635
28204
39326
36624
11780
28403
40069
35125
15951
28643
22653
33125
19111
55110

result:

ok 39 lines

Test #15:

score: -100
Time Limit Exceeded

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: