37pts玄可选择性壶关求条
查看原帖
37pts玄可选择性壶关求条
1036180
ChampionCyan楼主2024/9/5 18:25
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, m, mn, dis[505][505];

inline int read() {
	int x = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9')
		ch = getchar();
	while (ch >= '0' && ch <= '9')
		x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x;
}

inline bool check() {
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				int w = dis[i][k] + dis[k][j];
				if (dis[i][j] > w)
					dis[i][j] = w;
			}
			if (dis[i][i] < 0)
				return true;
		}
	return false;
}

int main() {
	int T = read();
	while (T--) {
		n = read(), m = read(), mn = read();
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				dis[i][j] = INF;
		for (int i = 1; i <= m; i++) {
			int u = read(), v = read(), w = read();
			if (dis[u][v] > w)
				dis[u][v] = w;
		}
		for (int i = 1; i <= mn; i++) {
			int u = read(), v = read(), w = read();
			if (dis[u][v] > -w)
				dis[u][v] = -w;
		}
		if (check())
			puts("YES");
		else
			puts("NO");
	}
	return 0;
}

Hack:

input:

5
50 100 10
36 12 384
33 24 3900
5 14 3354
5 7 9
21 37 727
43 19 6717
20 22 5295
23 44 4746
35 33 3765
46 32 9214
22 47 756
46 22 667
5 46 8284
1 26 826
26 44 7545
23 21 1518
33 4 963
29 30 8912
41 41 1586
26 49 1889
13 32 7405
9 36 7816
45 49 1716
30 45 6694
29 14 724
24 28 8008
23 28 2165
1 50 2028
20 30 4889
44 44 2493
21 1 9973
7 37 4839
1 11 3228
20 49 5844
47 44 4206
50 11 8547
6 32 4391
40 16 308
38 36 3685
16 26 6522
34 36 629
7 29 3458
22 6 9656
43 6 7664
50 1 4392
43 4 6385
22 44 777
20 2 133
8 7 5418
34 24 7470
6 15 5688
9 33 6206
16 20 5184
25 50 1875
21 13 352
26 12 6261
32 37 5176
21 47 254
22 41 6372
42 16 8734
17 50 3447
42 11 9816
25 28 7005
13 45 8013
34 41 3970
19 41 5169
35 13 8996
46 33 9277
48 29 3772
14 40 7971
12 45 7816
24 45 5746
2 2 5974
9 13 5041
19 2 3256
39 32 8967
19 43 700
15 24 4495
38 6 3617
15 1 9058
50 37 8112
10 26 3550
40 45 8266
6 27 7979
31 18 578
34 28 4978
1 27 1480
39 15 9290
24 24 6253
45 21 3162
22 27 5606
19 27 6222
47 18 2689
18 8 1186
17 29 4923
11 17 2245
35 47 354
45 41 1685
25 2 1624
33 50 4224
31 14 101
50 29 837
35 31 1263
33 26 1215
24 43 1628
16 31 708
16 26 754
44 19 104
27 20 1704
5 35 1991
50 100 10
16 35 1460
1 49 596
1 8 4754
34 30 2674
47 38 4676
43 1 5298
22 46 3342
11 16 980
17 42 7876
2 24 345
28 9 617
38 34 4487
4 45 5437
12 12 397
35 18 8842
47 38 4530
48 29 6270
11 3 1324
27 20 3611
18 1 4579
50 22 7623
34 32 2165
17 13 8081
15 18 9720
27 6 9011
38 21 9513
46 32 9480
36 19 4449
50 5 3884
49 49 5709
27 19 7090
23 42 7261
44 38 1344
40 43 1575
46 16 687
9 32 9215
15 41 419
17 47 9627
50 19 3997
6 18 7977
18 47 9070
44 4 2136
11 49 2882
13 30 480
16 10 7824
44 36 2124
40 28 8932
25 48 1456
32 13 8471
13 2 1055
24 49 5641
40 26 6511
14 22 3581
27 21 6149
26 3 1414
4 30 4699
10 13 2508
20 2 9716
11 17 3157
45 50 5896
13 37 2618
31 9 47
22 41 2186
19 49 5660
40 1 4598
29 35 2729
39 5 7974
7 27 2184
30 50 4002
31 44 865
24 43 4553
41 34 6063
37 25 7644
39 13 6076
8 33 6912
39 37 2368
47 19 257
41 14 6764
2 30 1794
12 41 8946
11 42 9718
33 38 539
8 29 9916
23 39 5676
33 43 7926
18 24 3979
5 27 4649
9 27 8292
46 28 1714
44 36 5755
37 14 5020
28 3 440
3 45 4164
15 45 7127
33 36 6306
29 23 5823
4 17 9559
41 18 2583
7 30 1364
8 10 5503
14 30 665
47 2 679
39 45 269
46 28 1526
28 48 46
32 17 847
11 6 1429
34 36 1931
13 31 155
24 3 747
50 100 10
28 39 6502
4 34 9705
7 28 8930
42 41 967
20 16 7895
30 13 122
37 2 5110
22 36 1536
33 40 3262
4 50 8732
42 28 9917
46 13 4525
41 42 8594
33 6 6459
9 4 1812
23 31 2507
4 19 9504
41 16 3285
43 6 3863
48 2 6561
3 12 8966
33 19 851
48 44 6817
37 13 1551
39 46 7444
17 16 5574
14 8 5125
1 21 1637
34 15 6507
38 40 5768
13 9 7264
25 4 3315
15 48 3598
23 25 9670
24 43 1466
33 33 1289
37 36 2599
23 5 1950
10 1 8743
3 26 2627
14 27 2193
28 38 9283
19 24 9297
40 30 8665
33 50 5411
17 5 6361
43 47 8499
3 17 2564
12 8 497
50 36 3590
48 8 1993
42 6 2169
21 4 3771
14 23 4995
14 20 1532
43 49 9530
25 5 9132
13 49 4052
21 29 6850
12 20 6850
43 2 1622
3 46 1806
7 21 775
26 3 3419
42 17 9899
23 8 2729
42 9 4168
3 34 9722
27 4 840
8 24 6233
39 30 5179
1 10 7682
35 23 8822
35 49 3637
21 29 9519
5 28 7031
29 24 6901
22 31 1619
3 1 8342
25 2 4180
25 5 5208
24 19 5557
27 40 5665
13 42 4627
1 43 5737
47 14 5714
24 27 3250
35 5 4628
40 2 5668
4 9 7906
7 37 9606
42 13 3663
28 26 583
11 25 418
21 44 8757
8 9 5191
28 35 6904
47 17 8683
20 7 7653
39 29 7577
35 30 1213
9 31 1696
32 41 1556
37 26 884
6 42 1577
46 41 1902
36 16 1348
24 2 325
27 34 723
23 38 1317
50 100 10
21 50 4411
11 12 509
31 6 1586
36 1 9868
20 38 9690
4 19 384
11 34 408
2 6 3154
34 18 6665
9 7 3495
39 40 5649
34 7 6993
2 19 8597
32 42 9782
47 18 3311
48 35 8305
6 27 8040
13 19 1211
37 6 8338
11 25 6965
9 17 1260
41 46 6183
25 12 5980
15 6 9143
37 49 5093
40 30 9379
21 34 9177
4 37 9439
45 4 1845
3 38 6838
46 40 9632
1 19 2380
46 30 1537
13 2 6148
43 1 3339
11 45 4355
10 11 4398
32 35 7997
3 26 9024
2 36 6506
49 19 2550
21 30 319
12 16 9799
39 45 18
24 10 7280
10 27 9405
2 12 7212
9 39 6695
40 32 8447
13 24 2074
30 25 9990
19 47 144
14 14 2919
35 36 929
16 5 1120
14 36 9525
33 25 601
24 42 9180
14 33 3343
33 24 602
48 15 1346
22 41 1638
25 14 3113
18 35 7669
14 21 5269
20 33 8315
40 50 1216
32 41 565
3 9 6791
32 1 6540
37 22 3818
47 44 3695
49 13 5745
30 50 9016
6 14 2138
42 13 950
35 4 155
26 45 8171
32 50 9680
50 4 7043
11 28 392
31 22 694
39 4 8734
34 5 5830
30 23 9089
28 20 4151
18 11 2245
11 16 1535
35 27 3064
5 13 4799
45 46 7465
41 48 2164
32 46 7138
3 38 5668
42 13 7092
49 32 5199
8 22 4038
34 47 9238
33 33 4252
22 21 7945
3 10 473
46 19 213
40 33 418
15 32 911
35 43 1809
26 4 242
29 2 478
39 42 187
22 28 1206
42 46 727
50 100 10
16 2 1035
43 32 626
46 3 1105
6 16 6468
10 6 7720
28 49 2992
26 33 7299
32 21 7609
22 16 6165
25 13 9865
18 34 4443
26 15 2535
15 2 9402
45 17 3280
18 49 2952
14 11 1721
8 48 6739
5 44 7925
35 4 2402
12 26 4776
42 46 8779
44 17 7611
40 13 1745
8 27 6839
27 12 9283
31 34 7365
10 39 3911
22 35 1175
14 28 2442
38 8 5998
8 30 9636
26 7 2298
25 32 9677
14 9 960
36 9 8056
33 3 9606
44 33 9280
44 15 9095
37 44 7367
17 23 485
24 4 8214
33 48 6825
22 20 5046
47 12 3919
4 33 3511
43 2 3918
7 35 7415
10 12 4379
31 23 2676
1 31 6198
10 35 7048
22 8 2003
27 22 7963
31 14 6962
12 19 3783
23 18 1027
20 30 7875
9 6 3841
13 45 5199
18 45 4211
37 20 3999
39 23 7923
13 17 2712
13 35 106
8 6 823
34 37 6187
38 13 5148
5 20 3776
8 46 5378
15 24 9349
46 41 185
37 9 2860
26 28 8083
22 18 773
46 26 7776
2 44 4611
44 45 4404
40 31 1840
18 3 3393
22 9 994
17 45 3242
10 45 3695
49 36 7077
38 35 9853
18 50 7638
6 13 3336
18 2 427
38 25 1660
50 32 7333
34 21 2494
29 39 2621
34 20 8781
18 49 4722
43 21 2546
37 13 5427
3 19 9662
6 35 4232
48 25 6560
32 38 5658
27 15 8694
11 28 1226
26 34 206
20 37 376
41 46 713
3 50 928
13 40 858
4 43 1367
50 13 1563
32 29 1204
20 29 716

ans:

YES
NO
NO
NO
YES
2024/9/5 18:25