QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#671857#2879. Kaleidoscopic RouteIllusionaryDominance#AC ✓69ms11164kbC++202.3kb2024-10-24 14:44:552024-10-24 14:44:56

Judging History

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

  • [2024-10-24 14:44:56]
  • 评测
  • 测评结果:AC
  • 用时:69ms
  • 内存:11164kb
  • [2024-10-24 14:44:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
const int M = 2e5 + 10;

struct edge{int from, to, c;}eg[M << 1];
int front[N], num;
void add(int x, int y, int c){eg[++ num] = (edge){front[x], y, c}; front[x] = num;}


int dis[N][2], maxs[N][2], mins[N][2];
int n, m;

void init(){for (int i = 1; i <= n; ++ i) dis[i][0] = dis[i][1] = 1e9;}

int ans;
deque<int>v;

void bfs(int s, int t){
	queue<int>q;
	
	init(); for (int i = 1; i <= n; ++ i) maxs[i][0] = -1, maxs[i][1] = 0;
	dis[s][0] = 0, q.push(s);
	while(!q.empty()){
		int o = q.front();
		q.pop();
		for (int i = front[o]; i; i = eg[i].from){
			int to = eg[i].to;
			if(dis[o][0] + 1 == dis[to][0] && maxs[to][0] < max(maxs[o][0], eg[i].c)) maxs[to][0] = max(maxs[o][0], eg[i].c), maxs[to][1] = o;
			if(dis[o][0] + 1 < dis[to][0]){
				dis[to][0] = dis[o][0] + 1;
				maxs[to][0] = max(maxs[o][0], eg[i].c), maxs[to][1] = o;
				q.push(to);
			}
		}
	}
	
	for (int i = 1; i <= n; ++ i) mins[i][0] = 1e9, mins[i][1] = 0;
	dis[t][1] = 0, q.push(t);
	while(!q.empty()){
		int o = q.front();
		q.pop();
		for (int i = front[o]; i; i = eg[i].from){
			int to = eg[i].to;
			if(dis[o][1] + 1 == dis[to][1] && mins[to][0] > min(mins[o][0], eg[i].c)) mins[to][0] = min(mins[o][0], eg[i].c), mins[to][1] = o;
			if(dis[o][1] + 1 < dis[to][1]){
				dis[to][1] = dis[o][1] + 1;
				mins[to][0] = min(mins[o][0], eg[i].c), mins[to][1] = o;
				q.push(to);
			}
		}
	}
	
	for (int i = 2; i < n; ++ i){
		if(dis[i][0] + dis[i][1] == dis[t][0] && ans < maxs[i][0] - mins[i][0]){
			ans = maxs[i][0] - mins[i][0];
			v.clear();
			v.push_back(i);
			for (int o = maxs[i][1]; o; o = maxs[o][1]) v.push_front(o);
			for (int o = mins[i][1]; o; o = mins[o][1]) v.push_back(o);
		}
	}
}

void solve(){
	num = 0;
	for (int i = 1; i <= n; ++ i) front[i] = 0;
	cin >> n >> m;
	ans = -1;
	for (int i = 1; i <= m; ++ i){
		int x, y, c; cin >> x >> y >> c;
		add(x, y, c); add(y, x, c);
		if(min(x, y) == 1 && max(x, y) == n) ans = 0, v.push_back(1), v.push_back(n);
	}
	
	bfs(1, n); bfs(n, 1);
	if(v[0] != 1) reverse(v.begin(), v.end());
	cout << v.size() - 1 << "\n";
	for (int o:v) cout << o << " ";
	cout << "\n";
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T = 1;
	while(T --) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5592kb

input:

6 8
1 5 2
5 2 5
3 5 4
1 3 10
3 4 6
4 5 7
4 6 8
2 6 1

output:

3
1 5 4 6 

result:

ok 3 6

Test #2:

score: 0
Accepted
time: 1ms
memory: 7868kb

input:

10 20
1 9 34
6 3 80
7 3 15
5 4 73
4 1 42
8 6 92
2 10 25
4 3 8
9 3 79
3 1 11
9 2 74
10 1 83
3 2 6
10 3 38
10 4 48
1 5 38
6 2 43
4 2 55
8 7 90
3 5 4

output:

1
1 10 

result:

ok 1 0

Test #3:

score: 0
Accepted
time: 1ms
memory: 5580kb

input:

24 65
22 11 519
2 4 585
8 17 647
1 11 464
13 4 596
12 10 733
24 21 106
1 14 345
23 5 430
2 3 137
16 7 891
16 4 807
14 3 465
4 22 532
16 9 346
21 8 859
18 15 631
9 5 914
19 17 729
1 2 546
5 15 43
2 12 349
19 9 642
13 3 441
20 15 359
21 11 645
9 14 992
4 23 9
23 9 34
24 16 117
16 18 349
10 22 285
22 5...

output:

2
1 11 24 

result:

ok 2 208

Test #4:

score: 0
Accepted
time: 1ms
memory: 5828kb

input:

53 123
43 38 999
7 24 718
6 33 393
16 15 734
21 39 604
27 15 828
45 31 747
23 4 538
14 41 224
38 9 756
12 36 574
12 13 624
7 34 649
17 53 309
38 33 825
1 36 273
38 21 81
36 11 680
14 8 649
12 24 346
21 49 921
1 47 612
11 39 648
41 35 271
15 24 36
29 3 980
29 28 295
15 21 236
27 8 853
22 6 532
3 14 9...

output:

2
1 52 53 

result:

ok 2 482

Test #5:

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

input:

2 1
2 1 33

output:

1
1 2 

result:

ok 1 0

Test #6:

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

input:

123 1032
49 28 6306
70 79 6579
24 47 3306
102 114 7381
78 34 4078
31 92 2591
114 65 7836
92 59 7583
110 51 4384
84 99 439
78 48 77
23 77 6225
96 69 2939
55 112 45
48 29 4735
27 18 4242
117 97 395
71 64 2979
102 36 9531
20 86 7795
11 5 3142
114 107 1188
62 106 6321
6 71 2974
102 96 4240
82 13 7488
95...

output:

2
1 93 123 

result:

ok 2 5258

Test #7:

score: 0
Accepted
time: 3ms
memory: 7660kb

input:

1342 23134
757 512 65447
281 782 35017
179 633 86323
707 635 20673
1225 962 76138
986 59 62123
29 482 39870
90 265 65928
572 1028 18186
810 568 89715
469 998 95978
583 641 63660
261 208 37031
775 1131 33707
161 702 33733
1340 726 67611
548 583 9224
1100 208 82846
227 486 60094
1070 565 49959
1285 11...

output:

3
1 669 616 1342 

result:

ok 3 93825

Test #8:

score: 0
Accepted
time: 23ms
memory: 7736kb

input:

5313 87123
3239 37 964433
3078 247 435023
1830 493 489819
4478 1661 914186
750 2703 353434
3853 1072 285309
2117 1377 641750
1254 4366 734040
2222 2191 362794
3461 2267 359296
2514 913 627160
878 1006 709645
1767 3791 250153
4845 4041 339269
3270 2061 26968
2421 660 798388
262 1399 974636
5120 4171 ...

output:

3
1 3463 3294 5313 

result:

ok 3 878139

Test #9:

score: 0
Accepted
time: 47ms
memory: 10220kb

input:

12313 173254
4620 6513 380927
4465 6551 243296
615 9825 794381
338 11211 368032
4571 9567 634707
3731 7430 87826
8106 7718 998064
4146 7848 922789
3966 1263 331881
9179 646 948846
11893 5020 883102
5612 10513 898068
3451 3435 451139
9640 1947 1353
12271 9668 283149
9742 5631 884826
6837 2449 309976
...

output:

3
1 1402 3350 12313 

result:

ok 3 497061

Test #10:

score: 0
Accepted
time: 65ms
memory: 10444kb

input:

23532 200000
21979 22532 52608855
17378 1428 55313979
12897 6506 2960978
21412 2936 26201355
1327 21400 71454522
6940 9953 7548221
15846 15164 69193724
22756 8774 49306072
10793 7975 94773768
15722 221 88298496
274 22685 29319966
21564 10196 30589888
2895 9073 93905131
8310 22526 13817682
1565 2616 ...

output:

4
1 18111 9089 18380 23532 

result:

ok 4 93767115

Test #11:

score: 0
Accepted
time: 69ms
memory: 10660kb

input:

56043 200000
8956 48459 891115255
34699 29270 626119743
15612 49268 833711278
35090 40312 12951690
27544 40981 509660868
32984 29979 910590843
54449 18153 383011987
36405 52382 871189321
22735 40079 205544352
1579 34250 703531988
1733 44402 554010888
11931 21887 65967217
7150 29324 904513650
55402 4...

output:

6
1 27483 27883 37006 9501 26651 56043 

result:

ok 6 960310393

Test #12:

score: 0
Accepted
time: 31ms
memory: 9760kb

input:

100000 99999
16259 89189 677093403
78250 8073 458212862
57547 91624 275388547
61506 43428 213190761
19202 93628 867133431
39385 53296 668727622
16499 67293 611076654
41619 33235 854029781
13362 34905 113954233
52118 36368 107607827
10583 42580 534654035
86638 25330 709240484
52574 8418 111555367
767...

output:

13
1 32645 7845 51316 29812 10607 72877 5776 79952 16297 43702 9206 88402 100000 

result:

ok 13 861759213

Test #13:

score: 0
Accepted
time: 59ms
memory: 11128kb

input:

80000 200000
58330 43217 297444461
16896 51153 140513289
9385 49460 443143629
69429 43934 531903821
26079 74229 736987435
51036 31562 159062344
41578 13401 929067646
55379 23507 690768049
30121 23885 877254400
35892 23458 465046769
34835 48337 668330315
18408 46981 120331309
44840 17333 120558928
54...

output:

10001
1 2571 56736 29497 58423 13231 62190 51844 23302 71875 36632 56046 12044 11399 21161 30678 41176 17250 74887 16470 71236 54348 19395 32369 16643 70641 60017 79306 2784 24319 22018 57742 20892 18547 48807 53000 75416 74602 2504 3613 5681 45251 4929 17827 63327 47374 5701 58964 51644 62943 24620...

result:

ok 10001 999977783

Test #14:

score: 0
Accepted
time: 64ms
memory: 10352kb

input:

60000 200000
33283 34451 984421794
1133 8529 735428179
49802 39150 2961459
35859 13866 164824146
53088 47966 338728371
51735 46841 957631316
35617 44579 765390527
31869 47907 947697615
32863 18985 25810436
3919 33953 460709820
15114 27802 873789989
14839 33186 914923632
51128 13349 457123147
22376 1...

output:

3001
1 54964 12064 31748 20995 31750 40188 50045 58670 31821 50806 13673 29233 21862 18050 14518 4985 10041 32998 52686 2199 34857 50551 45272 33846 8823 31428 57499 40761 24793 49589 15587 50398 3969 45626 26819 36968 31078 45949 11400 59127 11953 50239 18647 19142 26699 34660 55240 17376 44519 417...

result:

ok 3001 999993516

Test #15:

score: 0
Accepted
time: 64ms
memory: 10816kb

input:

60000 200000
26678 49495 904791977
32890 59699 399754622
12897 26396 947764101
20181 36060 919392167
44765 28112 626361389
20759 621 664654420
47334 52456 433569123
48369 19294 21978034
53174 8666 493354982
19124 57914 897565679
57051 48397 126735315
44750 56723 542440811
58365 39921 299193613
47535...

output:

1001
1 57442 20676 29999 34412 26870 31343 8646 35050 30130 22974 14530 4886 44237 17836 33014 23353 1337 36371 31665 20208 9484 21797 19025 41713 53138 11781 17974 20264 29548 54166 19805 21746 42252 53496 2185 26531 58552 44026 3169 21841 3805 33567 29328 30785 34863 48555 36289 12946 22164 33479 ...

result:

ok 1001 999983190

Test #16:

score: 0
Accepted
time: 67ms
memory: 10856kb

input:

60000 200000
13030 38329 743952825
12152 25060 344237987
5142 49370 883991906
46162 353 24332994
23681 44887 192607371
29905 55905 2537031
60000 49101 932618139
32702 45796 289202695
23051 41656 727218918
16650 2928 788402888
48744 9687 107198229
6033 9276 870216942
52085 29079 468002227
47038 4289 ...

output:

101
1 54472 53080 11468 58841 8126 56005 5737 18687 22107 42219 53273 1463 19373 47888 49906 13038 28288 4899 18111 30241 36321 59731 30655 46112 42388 40912 7107 4316 23386 5909 32598 44610 49449 4631 21038 49479 37913 29734 15662 52157 19102 54055 28492 22275 27195 55018 3834 24228 54321 45575 296...

result:

ok 101 999995626

Test #17:

score: 0
Accepted
time: 53ms
memory: 11164kb

input:

100000 200000
7896 67005 744335823
85405 32336 702280723
932 10230 692822561
28090 13617 935482306
13719 79962 309957027
60358 66039 604973007
49580 98941 669698279
1601 38911 929879781
35115 49689 748307599
70574 40830 441539342
4234 27200 214000427
20461 27894 634342248
19920 34635 502770262
49809...

output:

38017
1 28852 95874 9812 54966 75438 47471 94209 32680 82983 4579 2166 15386 54302 91762 83234 17839 96658 45337 99524 11093 91004 59139 527 76366 15151 85650 23512 5336 47343 60277 32356 18201 78324 73432 10981 43942 23018 39415 52735 47956 307 92401 76321 27164 16552 68931 70166 38666 10231 20509 ...

result:

ok 38017 999988667

Test #18:

score: 0
Accepted
time: 42ms
memory: 9632kb

input:

100000 100000
47771 2245 858688810
19704 38623 123305252
72092 57928 629702105
19730 42283 503649158
3318 40645 865792740
70657 92619 158522375
36552 21529 702477909
13169 56667 37832573
55245 83413 207618733
88975 85459 949034495
2236 31719 841176310
14025 81513 915364558
12564 50044 744295428
3688...

output:

66680
1 76270 31837 98546 56329 34221 11994 73277 88130 98743 36600 73257 82763 15736 29585 9528 11683 38834 41176 72299 91764 18531 34459 1038 13635 40968 20488 804 60750 43126 91614 35120 98257 70185 97326 12284 85563 22265 84294 61459 64267 79230 94774 48844 56988 97737 86750 22835 91185 23623 17...

result:

ok 66680 999951042

Test #19:

score: 0
Accepted
time: 46ms
memory: 10032kb

input:

100000 99999
66977 30908 949435071
54190 72909 999205575
12113 33498 921933482
31601 57272 486107186
2532 81610 837858661
50855 92529 679975042
15525 36595 792129612
55428 54274 191405543
88797 99354 489731776
29479 1309 395259492
26559 56361 373252267
37689 27563 441866444
912 69903 258017542
3629 ...

output:

99999
1 1593 26569 95095 22126 68838 40403 40406 72740 76054 66745 95972 1017 25878 6716 37938 33253 44638 37523 36809 1302 86319 46378 14173 36723 40501 81729 14652 47035 90261 28649 52412 60433 2189 8358 36452 16254 31268 62705 96896 95387 81970 68488 91438 85220 96368 36270 89646 90044 63585 3877...

result:

ok 99999 999976813

Test #20:

score: 0
Accepted
time: 54ms
memory: 10712kb

input:

60000 200000
47285 10692 505691882
55541 58891 106240529
58919 52351 179647787
22993 38756 855676401
1188 21752 479331859
53804 20156 32533051
36571 51894 847819320
13732 16398 899099258
34870 11239 658097306
43221 34310 46804480
2396 16626 825241903
53718 18139 158174462
24822 35888 248874769
38814...

output:

12963
1 45834 55070 25674 16053 48458 37855 47668 22644 39419 19877 44823 1405 41401 47272 54944 10113 6285 27438 36566 23593 15797 26905 53893 7133 11869 14511 5307 26230 57060 56124 2020 29580 58950 26623 11072 6703 44181 36538 17068 38959 55516 10734 41586 3196 49674 4028 11682 58615 19404 46312 ...

result:

ok 12963 999980538

Test #21:

score: 0
Accepted
time: 50ms
memory: 10956kb

input:

60000 200000
52075 45966 857582124
57572 4850 910824716
36159 50425 950606070
9851 34403 5047521
21825 21680 424988833
53325 44593 135616766
23579 36275 607428614
864 4421 991903370
54798 24959 706926183
19713 1269 755420688
27732 39509 234793607
15664 44127 163234400
10226 49453 658379227
39921 861...

output:

6853
1 39081 49146 25559 35202 12215 38608 2423 31422 35479 32626 43342 21083 4910 26713 42182 8110 29670 19702 6229 39725 46541 35736 27017 32366 7102 31177 23247 12257 46802 21720 1553 57191 18492 23444 9517 4892 19839 57922 3959 46295 7317 48322 21521 50073 8948 27503 40113 40882 55810 1231 17891...

result:

ok 6853 999981487

Test #22:

score: 0
Accepted
time: 54ms
memory: 10776kb

input:

60000 200000
1891 47162 951536190
36752 59437 440609838
59002 27483 924865044
13384 34668 194909776
9403 44772 573169297
15690 13096 653635499
17522 3611 411664894
20460 58639 710963529
41109 13541 354810632
16256 22124 899771391
13628 11173 231927636
13824 32461 275047309
39397 38605 1849131
20192 ...

output:

696
1 7542 24380 21257 15738 30839 16449 58893 59627 19268 1781 6942 49944 44452 22247 8241 50057 19425 50250 40592 7950 31447 36723 48182 33612 30026 34984 23664 25716 4760 56759 10312 700 8459 31673 55768 20191 10987 9218 18852 7730 33249 15975 25046 52088 15363 21989 34888 32354 57243 1107 39405 ...

result:

ok 696 999850312

Test #23:

score: 0
Accepted
time: 67ms
memory: 9564kb

input:

632 199396
520 52 920959168
625 184 3419342
387 412 429471383
83 163 185930246
530 428 63660253
631 447 521883183
261 602 466912409
340 419 539676608
308 131 760529469
333 488 204935294
582 272 755853621
59 116 129089400
584 76 197908036
285 107 255363470
595 352 367975615
152 201 737292798
347 297 ...

output:

1
1 632 

result:

ok 1 0