fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void letsgoo();
  5.  
  6. int cost[1005][1005];
  7. int G[1005][1005];
  8. int visited[1005];
  9. int n , r;
  10.  
  11. int state , road , rail;
  12.  
  13. int main(){
  14.     int t , kase = 1;
  15.     scanf("%d",&t);
  16.     while(t--){
  17.  
  18.         for(int i = 0 ; i < 1005 ; i++){
  19.             for(int j = 0 ; j < 1005 ; j++){
  20.                 cost[i][j] = 0;
  21.                 G[i][j] = 0;
  22.             }visited[i] = -1;
  23.         }
  24.         scanf("%d%d",&n,&r);
  25.         int x_axis[n], y_axis[n];
  26.  
  27.         for(int i = 0 ; i < n ; i++){
  28.             int x , y;
  29.             scanf("%d%d",&x,&y);
  30.             x_axis[i] = x;
  31.             y_axis[i] = y;
  32.         }
  33.         for(int i = 0 ; i < n ; i++){
  34.             for(int j = i+1 ; j < n ; j++){
  35.                 float dis = sqrt(((x_axis[i] - x_axis[j])*(x_axis[i]-x_axis[j])) + ((y_axis[i]-y_axis[j])*(y_axis[i]-y_axis[j])));
  36.                 cost[i][j] = abs(round(dis));
  37.                 cost[j][i] = abs(round(dis));
  38.             }
  39.         }
  40.         state = 1 ; road = 0 ; rail = 0;
  41.         letsgoo();
  42.         printf("Case #%d: %d %d %d\n",kase++,state,road,rail);
  43.  
  44.     }
  45.  
  46. return 0;
  47. }
  48. void letsgoo(){
  49.  
  50.     vector<int>v;
  51.     v.push_back(0);
  52.     visited[0] = 1;
  53.     while(v.size() != n){
  54.         int x , min_cost = INT_MAX;
  55.         for(int i = 0 ; i < v.size();i++){
  56.          //  cout << "COMING FROM  " << v[i] << endl;
  57.             for(int j = 0 ; j < n; j++){
  58.                 if(visited[j] == 1 || v[i] == j){
  59.                     continue;
  60.                 }
  61.            //     cout << "     GOING TO " << j << " COST : " <<cost[v[i]][j] <<endl;
  62.                 if(cost[i][j] < min_cost){
  63.                     min_cost = cost[v[i]][j];
  64.                     x = j;
  65.                 }
  66.             }
  67.         }
  68.      //   cout << "SELECTED :  "  << x << " COST : " << min_cost <<endl << endl;
  69.         if(min_cost >= r){
  70.             state++;
  71.             rail+=min_cost;
  72.           //  cout << " ++ AND RAIL\n";
  73.         }else{
  74.             road+=min_cost;
  75.            // cout << "ROAD" << road <<endl;;
  76.         }
  77.         v.push_back(x);
  78.         visited[x] = 1;
  79.     }
  80. v.clear();
  81. }
  82.  
Success #stdin #stdout 0.03s 23944KB
comments (?)
stdin
copy 
20
87 35211
9263 -9865
-6374 680
9947 7021
-6335 5766
5003 5761
-4544 -493
6843 3305
6601 5419
-8436 -4239
1293 -9761
-4585 3826
5463 6981
-1185 -4686
-4044 4089
8641 5832
9689 -8293
6108 -8377
-7636 -2965
-7200 9775
9257 -3971
9258 -8477
4828 -5288
-9870 9821
-4419 1428
5389 -8305
9242 6874
7576 -9197
-162 8425
6234 111
-337 5794
-8778 4874
-9782 3072
-9894 7330
-9175 -7418
2333 -3372
1872 -9919
-1486 1590
5131 -3300
-8152 -1356
4060 -9289
-8694 7237
-8240 3302
1726 -7398
2713 1598
-2608 -2040
-3446 -7625
5448 -1386
-336 -3228
3076 9275
-377 489
4291 -4592
-9282 -8505
1916 -7196
5170 5849
6560 3764
4722 -771
-3749 -8414
-5812 6482
-1920 -8302
3379 -9379
-7003 9193
-2194 9933
426 -7835
-4840 -8810
1680 -6499
2630 4784
10000 -309
2496 3348
-804 1915
-601 -2335
-9386 -524
1063 -5880
-5677 -3134
-1436 8972
9594 6124
5316 -8058
-4405 -3689
-1524 -6879
-1968 6021
-6758 7357
5861 9712
3124 5872
2940 5860
1495 -660
-9275 -7865
5333 -9106
-1265 -8661
5 15174
-913 3058
-819 -9511
-3848 -1320
4991 -5504
1338 1748
65 35806
-5456 9371
-7198 4732
4324 -9596
9986 5926
-1014 985
6841 1480
6095 -289
1051 2173
-7712 -5170
-8392 -7024
-6534 1376
-9945 790
9007 3339
-4914 5047
-4046 4066
7157 6576
5028 498
4624 9959
9606 -649
-9665 8330
3530 -1409
-7977 -9103
3070 -375
8176 3074
9771 5359
455 9784
4294 -3043
-9704 510
-723 7022
4808 -4618
-8043 8953
3171 1964
5643 -9295
57 -2206
-156 8969
-2440 4113
8731 -2905
6720 3304
-3623 1801
880 8616
-7881 -132
6826 -8666
5565 -9866
7156 7122
-7497 -1437
-2485 5684
-2353 -1818
-1113 -9315
2201 -6711
-7742 -7336
-9502 -7956
-861 3539
-3158 9229
1029 -421
1915 6940
-3193 -4371
-3037 4035
7890 -6368
-9247 -3751
4812 8766
4449 -3022
5160 -7674
-6989 -7905
-895 -2233
432 5212
87 36982
-1378 930
158 3837
-2863 5464
6124 -5092
537 9052
6807 -7069
284 -8779
-2530 4696
7182 4759
-8264 -3998
-1672 1630
3725 -9384
-1617 5060
3993 -7170
7914 8815
3465 4970
2527 -3464
-4280 -2656
5973 -6616
-3843 -8156
-1504 230
1451 -7037
-8620 -7500
7259 -7359
2364 8562
3913 8995
-6669 -9309
9473 -2363
4188 1715
4250 3465
2155 2102
-7642 1436
8780 -1598
1787 -1922
3643 8473
-1298 7944
-5373 -7862
-5361 -6126
236 -3993
-1710 -4382
-5387 -7400
-2988 -7798
3560 1665
-6621 -3516
-6331 1469
-6430 -8650
2786 5824
-5774 -351
7727 5286
3758 6013
3956 1370
7229 -7541
54 8583
-1689 -4412
1207 -9710
-3389 -9679
-3756 9541
1205 3623
-6172 -6476
4993 8306
9656 -2503
-6679 -7717
1932 2441
-2274 1268
1001 3380
-1530 -8517
-2337 -1323
980 -581
8729 -8562
-8272 -6989
-6668 -65
3196 2060
-4318 3297
-9458 -1879
-3574 -490
-9272 5535
-8461 -198
-7758 -5951
9038 7192
4292 3689
5172 38
8715 -7239
5902 -3444
-2006 -306
2706 4630
-1715 3443
-4498 9759
63 37645
3322 4905
-1864 7319
6574 9749
-450 -1136
6634 8113
9026 5514
-798 5671
-4292 3317
9800 -1905
8372 -1857
7837 5701
330 -3635
-6472 4263
4022 8615
-6185 2751
-2345 798
-1884 7137
-9395 5791
-1625 -5311
-3477 3877
-610 -4992
-9322 -731
-7415 -7688
407 107
8250 -3895
-8195 2499
8864 9808
4070 5856
8191 -3888
8863 -1909
-7391 -7995
-7137 -3482
-3971 4446
-7144 -6532
-8935 4405
-6867 -621
-7632 4176
6489 -2467
7640 -5047
1059 616
-6885 9611
9418 6585
2441 -4301
1812 3487
-4701 4352
6358 4395
-9088 1629
-3925 -7059
130 663
-1212 -1069
-7970 1196
-4629 1921
9454 -5602
3072 -4420
6197 -9186
-9576 -2149
-1843 -6968
-1269 9842
7049 -9403
4949 -5737
8659 -3932
7698 5027
7968 -6709
98 24805
6424 1819
-6986 -3538
-7896 -7826
-3428 2106
-8593 -8443
-7629 -6636
1216 7604
-5644 -3484
-3643 9373
-6310 6808
-5208 -2873
3195 -7641
-8893 -6550
462 4613
-7895 -7205
4614 -1863
4599 -7751
-5577 -8652
3455 -9577
-4298 4716
8081 4862
6186 -1927
8311 3017
6110 -5738
-8931 -1612
5515 -6480
-400 -4139
3032 2431
764 707
3503 -6506
5352 2870
5119 1837
3186 3671
4095 -6737
7979 361
-1057 9797
1590 9780
6517 -4872
-610 -100
8289 2626
9867 4180
-6238 7524
3675 -533
-9827 6794
-5992 -5561
-8971 7397
-766 9360
3031 9869
-6869 -3860
6501 -2875
642 -5169
-5390 -4557
4292 -7769
2132 -8873
7474 -2598
-8419 4141
5385 7341
528 -4657
-4142 -940
3499 701
1819 -134
-774 8249
8117 -5227
913 -4023
3102 -8752
-200 -2587
2856 -6257
-305 4410
9258 868
8270 -4453
-6592 -9548
-8487 9851
-1085 8794
-2147 2041
-3538 4773
-5362 -4928
-2959 8281
-6947 7585
-6439 -4843
126 3966
-4901 6663
-5874 9926
8057 -8325
2543 7543
-6911 7314
-8514 812
4384 -3502
-988 -7001
5040 -6702
8071 6865
-4343 -8498
-6497 -3571
-5986 2698
-8425 -3443
-5757 -2425
-2041 1702
1627 -657
4739 5806
95 39912
718 -2718
-8186 -9842
377 2204
8925 6198
9496 9389
9974 3964
9187 -8714
1437 -4370
-7952 -7310
2968 5451
-3254 -2656
9046 -9069
3995 8426
4232 4394
-5924 -1266
9737 1300
5179 8515
4440 -8450
-8531 -4445
-5057 3364
1048 -5315
-4028 -5084
4267 235
6646 7409
6580 6315
-2620 3334
7986 -6675
-8249 -3575
-9182 1981
-5565 9704
4724 -1384
851 -5829
-558 -97
5458 -4710
-7626 911
5597 -9599
-4683 3423
-2622 -4711
-7303 9585
9620 -2256
-5202 -7003
-3678 -3001
7146 -7217
4764 1794
5218 -8316
300 -7081
-2910 -58
-6435 -5128
162 -9747
1164 9023
-6856 6258
-320 481
5770 -1538
1767 7058
-1478 -7813
-4816 1386
-7894 3320
6103 5228
742 9252
-9065 4588
7507 -319
9623 4957
-6451 -5403
-1429 -3092
-4070 7432
3689 9735
3937 -925
-8743 -6632
-5854 -294
5615 3024
-1870 2668
-4013 -9202
9747 3957
6929 -4189
-9602 4210
-6110 7865
6542 7905
-3778 -2767
4141 -9910
7522 4793
8249 -9930
2866 1211
8300 2185
-4389 4123
867 -3833
8835 -8775
-4255 -7282
6675 -1457
8075 -788
-6579 3604
5189 8473
-9903 -2689
8265 5451
9262 41
-1446 2405
82 1208
1714 -3198
-7293 2783
627 3735
9902 2040
6986 -8507
-2068 -7544
4720 -7270
1943 -1672
-8069 2794
1266 9085
117 -9160
-9989 5085
-4875 -1619
-5493 9273
9776 3679
-5798 -9297
3486 1490
-1055 -3091
-7331 -5888
-673 -1154
1302 9656
-7615 7259
-693 -3978
8816 8049
-9146 4959
5799 3803
2608 4692
-3207 9531
8803 7733
1411 1300
5724 8579
3789 9334
-36 2931
-9237 -3546
5300 2633
2288 3811
4791 322
6344 8395
-9837 -5903
9057 8881
6404 -5262
9430 8576
8107 -989
464 -3777
7523 6909
9208 -8126
-5071 6968
-102 6717
-6830 4893
-2475 661
-5528 -7810
2513 -6466
-8072 9263
-6641 2577
5178 -4188
551 -3864
-5288 1581
-5688 -20
9924 -7182
-6553 4776
-9629 7447
4414 -3624
-6908 -4700
-9808 -1968
-7587 -16
2174 1438
4972 606
-132 -1593
-9016 -9380
-3567 6949
-6916 6162
1464 -9296
4405 1517
4335 5776
552 4329
1775 7783
-5842 923
9944 -91
-8339 971
-5325 -9865
1573 -5926
4681 6850
54 26632
886 -1731
-1062 3682
-156 -8961
-8257 5744
-2740 -4972
-9197 6149
477 -8405
-6902 5076
-4002 -4028
9602 977
-8053 -4059
-203 -8738
-943 -3377
-2807 -4909
5357 -6263
2007 9891
3573 -37
1003 -5335
-9592 -6584
-1556 6467
2615 -2331
2985 2968
-1956 -3188
6505 9804
780 7763
-2575 6106
-8912 6448
-3209 7222
-3967 146
3883 3984
7596 -8611
5074 -390
4276 1168
8305 -3924
-7458 8405
-3927 469
-6564 8879
-4310 -7222
-7419 5201
2964 -4084
-7979 3361
3530 -5891
-4949 -6890
3256 -9680
8026 1085
6195 859
-5810 5621
-3212 1268
7344 -7814
-9410 -4908
5561 -6393
-3794 385
3163 -7283
7919 5617
89 13511
6547 4603
8712 -6446
385 76
397 -6238
8568 -2639
-8060 -1578
-5958 4763
-3970 -3870
-1684 4551
9643 -2905
4423 2628
-6988 8924
-8360 -9372
6245 9896
9361 -6721
-8398 7778
-4948 5908
-4017 -9687
-2203 9158
-3482 -9900
-1478 -3636
-5153 2179
8310 6285
835 4599
-4586 346
-3306 477
3121 9837
-5815 -294
-398 8483
-4518 -9571
-8073 2683
2311 -2915
1119 700
3578 -7985
-7885 -7364
2722 -6184
5996 4359
643 7569
2167 8026
-1629 -8522
5676 7581
-8863 5066
-1508 2518
1000 -4678
-527 -8186
4498 6482
-2713 5121
-458 -3192
-1177 8407
-8958 -6881
-3064 4660
-982 3764
5054 -7069
-9044 9661
-5141 -2780
-1478 3048
1834 -9465
6774 3380
8703 -9674
-4139 -2227
-2025 1896
737 -5921
4609 5263
3669 -9722
-2881 -6569
-8189 8432
2196 7776
-9294 829
4211 -2751
8190 -4617
-7849 9070
-6675 432
-6188 3986
8033 -9902
1592 -3765
-8149 -6107
-2027 9568
4830 2588
6588 -7419
-267 2219
650 -6294
-8519 1545
-3906 -3434
7536 -4092
5012 -9696
9375 5726
-122 7163
4869 -3580
-3481 3690
86 9591
-9485 8111
-8602 -4504
8085 -1512
4790 6228
2167 8393
-7902 -1757
-6492 -7183
3104 -2700
6929 -397
3628 640
86 1940
-898 6723
-6857 9964
7375 -6029
-9408 3383
5214 -8981
-3484 -8893
3316 6613
2840 -1679
-3287 1826
-9931 -4993
1545 2532
9832 -6423
6901 -5352
9009 -9520
2420 529
-2749 -906
2779 -4758
2934 4115
-2503 153
4893 3527
8355 -7289
-6956 -8592
3450 5392
-2783 5884
-5389 -9838
2694 -2714
4585 9877
-1754 6246
6726 5206
-4266 975
-9931 2866
8109 6707
4542 6569
442 4763
2010 -4240
-1529 -4666
464 365
-4244 1515
1119 -6087
-5924 6694
-2299 9452
-6952 -9510
-9543 -7715
7491 1294
-7731 -9097
3770 -3054
-2627 -3941
-3652 5599
361 -8086
-2326 6790
-7877 -7629
6457 9866
5101 2587
-9779 -4067
-7374 -59
-608 -1982
2229 4048
-9947 2440
-2545 2686
7311 -8735
-1789 3445
9504 4801
4120 9305
-8782 -4149
-3639 -5520
572 2614
6200 2205
-1487 749
6682 1301
-8759 -1266
6752 -6971
7077 4354
514 -1020
-4613 7131
8396 -8311
11 15237
-8782 327
3352 8358
-2071 5338
-6462 8291
904 4290
-3505 4111
-1420 -2896
-7875 5008
-6259 -4738
2012 -2913
-4839 -5787
39 1428
-61 5675
7365 -3979
2439 2055
-3898 6219
4577 3657
2715 9454
7745 -7495
-9484 6254
4085 2369
-6807 -2989
-4261 -7336
1647 -961
6126 3201
7414 -6342
6468 -8714
-9318 8048
-5931 127
-4097 8047
4265 6508
3886 2005
5180 -1159
5068 -3400
-7147 6645
2734 5584
-3685 6938
-6677 5928
-5034 2054
-4746 4970
-7651 -5187
-3901 -3612
-1844 8817
2664 -3219
-1452 2225
2454 8567
4293 -3466
9096 -3661
6660 3193
-163 4163
3467 9514
26 5775
-7782 9782
1835 -2785
-7815 906
5719 -9191
918 -5466
-2929 -8183
2320 9075
5020 9735
-7978 -5412
1122 1194
7533 6315
3228 218
-1899 7914
-8853 -6936
-645 -8432
-8651 -8682
2255 5295
-3800 6906
-8565 4440
-7306 -8082
-2544 6075
8870 -235
-501 -6504
-1915 3889
-4917 5242
1556 9207
9 35522
-5751 -1496
1568 7526
-7186 -883
4157 -5356
-6341 -5837
-5211 -3589
-9150 -141
5498 -54
-3980 -6456
57 18154
-3550 -5111
-7502 249
-4509 4535
7462 -2419
7639 -9233
-728 607
-1868 -4392
4726 -5440
2925 4667
8830 -1118
5293 6584
-3558 -2660
7286 9864
-2872 -8061
-1386 -6695
1915 -5843
8127 5064
3319 4413
-8006 -6383
-5615 780
-8614 -6647
-1039 3657
-8063 3239
-2095 -2593
6289 4863
1446 456
-8484 5302
5165 -8391
-6452 8802
-4173 -3987
3891 2162
946 7742
5875 2018
5635 -5736
8766 7869
-5058 -6260
-8883 -6128
-9168 7625
-4969 -6945
7918 -1263
-7087 -4959
-9658 -637
4693 -1850
672 9229
-4759 8242
4124 6499
7961 9133
4871 -1209
6776 3836
5425 505
4246 5541
-6866 -5912
-8288 9084
-7862 -6034
6424 -3257
5505 -6224
6861 9338
53 33582
8797 1553
-206 -8120
8379 -2242
611 -2361
6430 -9940
7617 -4519
9708 3205
2467 6762
-9151 7674
6757 5601
9567 -7439
3026 8896
-7329 5990
9048 -1470
-1902 9532
1085 256
2136 -3106
8374 -5401
2238 4235
8016 -1016
4466 2388
-4407 5632
2394 4173
1846 -8220
7381 3243
9526 -1398
1218 6947
2936 2551
-5199 7611
-9138 1984
-4040 2900
-6486 5668
-9733 8096
2330 -8113
872 6226
2335 346
-302 -942
-6770 -8352
-6572 -4188
-7224 8797
1119 -9192
7755 -7699
8573 -3942
-2611 4411
115 -2906
9994 -1749
-6081 6075
7891 -2771
-884 -2093
-2147 3942
-5713 -6292
2766 -9813
-8165 7706
87 9060
-7767 -1016
-208 -3706
2316 3353
-6869 1267
-4322 888
-8298 520
8771 9514
9310 -8304
-1075 -3590
8038 7200
1141 -8239
-4530 -4109
-201 9149
6855 -8044
-8327 5356
-5661 -5907
387 -6094
-9021 4132
-881 -7298
7311 -5890
8351 4797
8032 9013
-5571 7122
-2748 7341
4540 7075
8837 -4710
4902 -4319
-1450 -1973
-17 -5300
-9945 -4596
-503 1656
9284 -1884
-7753 -6396
27 -9738
-1906 5087
3605 1058
3792 -3556
-2714 1636
-1024 8221
9017 8260
-2730 -2764
6638 -8427
-400 -7829
592 -4812
4313 -6697
8681 648
-7516 -2469
1135 7964
-8054 -1548
-6462 -8838
2220 3761
-6074 7143
-1222 -3989
-2047 1212
3192 -8526
2432 -3031
2263 -9539
-7368 -931
7978 -8138
-1114 3225
-2407 2291
9822 -2434
-4471 77
8529 4677
5839 1197
-5043 -4213
-7070 1780
-8489 -1117
-6184 5429
6904 3185
-9847 7008
-8810 3056
-7876 2416
7999 -6178
-9233 -6177
6114 -3115
8172 -1640
-7843 9656
4332 -2578
8619 -5594
194 3892
-608 -2704
9901 3124
-1448 903
-5912 -2563
-1835 -824
-7769 -2038
46 8086
3178 -1923
1900 -4182
6424 3945
-3974 1734
5110 4596
-7983 -1817
2590 3162
774 -5644
1652 -3496
9628 -9835
4790 5273
-7291 1900
-5203 -7402
4281 875
-9771 -2972
8826 -7900
-2081 3407
1073 725
-3821 -1937
-3621 -9181
2723 -8712
8172 -1604
2752 -967
5537 -1055
2832 -1875
-6603 8885
785 -2379
3940 -3893
6982 5582
-3670 -1780
321 -9069
8060 -1123
9602 -8040
3744 2853
3672 -498
4511 -9877
-1481 -3606
5428 2682
-4652 -5008
6838 964
3570 8180
-479 -6045
62 -5646
-6344 -6540
5401 764
5417 3707
46 4787
1402 3476
-3672 -4094
5408 -4854
-4731 10000
114 3639
-3679 7509
-3779 -738
-6053 1669
-152 -3221
735 7517
-8130 9369
-3451 -5483
9003 -753
-7047 -8051
1392 4419
-2106 -742
5164 -7207
1660 7943
-8338 4292
-2070 -9351
-8121 1776
-8962 7972
-360 -1900
4880 -5015
-7499 -6792
-3703 -665
3852 -1908
7339 2846
8517 2854
-2728 -5988
6991 -92
6422 8887
6829 2154
-3555 1803
2452 8491
267 8097
6068 8052
-127 5026
-9990 -571
2637 -5248
7808 -3768
4324 -7345
9222 1659
-5487 5383
-6885 7738
1366 5506
stdout
copy 
Case #1: 1 641064 0
Case #2: 1 23808 0
Case #3: 1 403255 0
Case #4: 1 489981 0
Case #5: 1 347190 0
Case #6: 1 590351 0
Case #7: 1 676307 0
Case #8: 78 3067 571872
Case #9: 1 299363 0
Case #10: 11 413287 172574
Case #11: 20 242844 265960
Case #12: 1 52553 0
Case #13: 35 3429 201974
Case #14: 11 52655 113321
Case #15: 1 75326 0
Case #16: 2 352720 20750
Case #17: 1 355969 0
Case #18: 12 301823 158275
Case #19: 13 124359 141663
Case #20: 26 46126 238612
https://ideone.com/kCcPfe
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!