HugoGiaohang
quoc14
c_cpp
20 days ago
9.7 kB
3
Indexable
Never
Backtrack
Level 4 Hugo Giao Hàng Hugo Giao Hàng Hugo đang làm việc cho công ty Samsung, tuy mức lương ở Samsung không hề nhỏ nhưng vì Hugo là lao động duy nhất trong nhà, vợ của Hugo mới sinh em bé. Hugo muốn kiếm thêm thu nhập để có thể có thêm tiền sữa, bỉm cho con. Hugo quyết định nhận giao bánh pizza ngoài giờ làm. Mỗi ngày, sau khi tan ca Hugo sẽ nhận N chiếc bánh pizza để giao tới N địa điểm khác nhau sau đó trở về nhà. Tuy nhiên do giá xăng dầu đang leo thang, Hugo cần phải giảm tối đang lượng xăng phải tiêu thụ, vì vậy Hugo muốn tính toán xem quãng đường đi giao bánh pizza từ công ty sau đó về nhà là ngắn nhất. Hãy giúp Hugo với nhé. Đầu vào T test case <=50 Dòng đầu tiên chưa 4 số Sx, Sy, Hx, Hy tương ứng là vị trí của công ty và nhà của Hugo trên hệ trục tọa độ Oxy Dòng tiếp theo bao gồm số N và N cặp số liên tiếp tương ứng là tọa độ các điểm mà Hugo cần giao pizza. N<=10 Cách tính khoảng cách giữa 2 điểm x1,y1 x2,y2 D = |x1-x2|+|y1-y2| Đầu ra In ra quãng đường ngắn nhất Hugo di chuyển từ công ty để giao bánh sau đó trở về nhà. 10 57 61 50 61 5 86 53 4 104 27 3 55 34 69 0 96 47 60 28 5 0 6 43 84 84 35 44 57 95 50 48 32 67 42 5 53 51 92 1 48 19 8 3 82 37 97 28 66 41 5 93 72 9 79 46 31 12 66 54 11 38 62 93 86 5 87 83 40 83 83 26 98 11 74 103 23 42 71 16 5 12 76 47 74 24 5 88 82 45 85 96 85 14 6 5 86 91 104 60 72 35 59 22 58 39 99 49 68 1 5 48 80 96 101 56 88 75 56 25 81 51 14 75 51 5 29 62 103 15 75 84 67 94 96 57 87 39 57 77 5 105 85 31 40 1 88 83 89 29 18 Case #1 393 Case #2 323 Case #3 267 Case #4 294 Case #5 281 Case #6 300 Case #7 219 Case #8 283 Case #9 295 Case #10 344 Case #1 393 Case #2 323 Case #3 267 Case #4 294 Case #5 281 Case #6 300 Case #7 219 Case #8 283 Case #9 295 Case #10 344 Case #11 3838 Case #12 3751 Case #13 3371 Case #14 2799 Case #15 3160 Case #16 2726 Case #17 2919 Case #18 3150 Case #19 2945 Case #20 2929 Case #21 3688 Case #22 3105 Case #23 2677 Case #24 2668 Case #25 2701 Case #26 3295 Case #27 3448 Case #28 3259 Case #29 3430 Case #30 3957 Case #31 3593669 Case #32 3069517 Case #33 3944363 Case #34 3948008 Case #35 3526834 Case #36 3234239 Case #37 4219447 Case #38 3403064 Case #39 3569497 Case #40 3935750 Case #41 3579617 Case #42 4134884 Case #43 3846356 Case #44 3651863 Case #45 3494954 Case #46 3907667 Case #47 3545049 Case #48 2625656 Case #49 3457166 Case #50 3560082 Time: 1.43600 s. 50 57 61 50 61 5 86 53 4 104 27 3 55 34 69 0 96 47 60 28 5 0 6 43 84 84 35 44 57 95 50 48 32 67 42 5 53 51 92 1 48 19 8 3 82 37 97 28 66 41 5 93 72 9 79 46 31 12 66 54 11 38 62 93 86 5 87 83 40 83 83 26 98 11 74 103 23 42 71 16 5 12 76 47 74 24 5 88 82 45 85 96 85 14 6 5 86 91 104 60 72 35 59 22 58 39 99 49 68 1 5 48 80 96 101 56 88 75 56 25 81 51 14 75 51 5 29 62 103 15 75 84 67 94 96 57 87 39 57 77 5 105 85 31 40 1 88 83 89 29 18 956 559 566 989 8 669 539 972 343 133 123 414 689 946 751 125 237 108 801 1004 124 925 285 895 600 8 711 176 526 309 309 319 670 282 166 924 41 41 595 447 691 683 429 15 958 11 8 375 828 545 54 139 662 193 413 435 719 97 515 578 911 364 511 692 892 949 524 8 515 666 881 436 209 441 154 363 109 436 862 356 741 184 5 638 302 480 54 688 8 895 690 254 137 490 507 787 963 267 215 381 766 950 833 431 545 5 562 740 203 8 569 955 880 828 477 600 575 955 747 226 469 1005 337 682 244 982 66 651 7 337 8 934 887 840 643 886 830 338 935 399 795 728 514 396 732 275 277 108 278 30 526 8 382 294 905 331 284 202 143 784 527 133 899 808 390 37 744 161 875 884 405 111 8 763 769 333 642 551 960 657 792 887 456 581 514 238 891 854 100 984 283 222 984 8 933 701 884 694 461 976 319 886 414 985 227 376 979 679 407 203 514 946 462 884 8 844 909 62 751 770 562 592 983 76 44 314 187 365 666 557 748 637 258 648 698 8 402 832 756 224 109 694 837 365 818 653 521 301 304 1002 799 977 102 683 60 110 8 160 449 486 657 172 814 533 300 362 789 367 558 618 171 305 872 725 484 845 354 8 113 317 104 299 662 458 6 868 129 467 402 783 406 306 315 304 852 493 406 710 8 421 957 327 945 495 750 451 560 359 656 89 678 665 754 263 351 513 630 847 623 8 169 930 295 297 396 276 267 126 759 16 944 475 858 378 487 721 855 649 53 473 8 174 786 499 271 178 341 276 442 870 54 382 476 704 792 779 851 252 497 828 936 8 374 834 1004 149 624 196 234 670 116 692 486 885 906 194 972 75 963 857 107 261 8 378 158 525 782 983 453 54 523 813 114 791 725 875 126 456 726 97 658 777 447 8 441 573 680 312 384 726 619 443 936 15 33 270 78 83 841 868 641178 228103 102168 270584 10 681356 41528 208638 966556 698793 653223 111000 288091 297165 839007 263942 429379 984022 16002 696622 622825 820684 983208 495758 940625 47571 33923 529583 704282 10 458510 125694 102712 728530 526611 554214 94299 767623 585236 375704 74322 244738 115090 675588 522383 950641 356277 368506 503064 928550 846100 39354 870990 563621 10 194107 826582 654016 380585 449654 315008 494527 115798 68940 323940 893830 443903 656036 518461 767709 979296 846922 242063 406945 382052 96004 729338 102646 747180 10 81876 435124 380444 573418 236565 238122 684466 735337 910500 395681 37954 259459 41590 931300 756061 814765 363078 160627 401725 105875 219789 618377 437502 538508 10 540338 663180 767808 491982 549371 162075 33532 68596 875098 463096 949785 484574 946821 128826 842602 415911 594486 848010 793248 94066 178136 308736 986333 215942 10 787164 181183 809324 211043 103748 11764 26639 403873 276646 887061 307259 860715 436438 886651 822332 756111 134866 268348 181910 931028 820591 331844 741725 48341 10 348057 338857 196402 774743 122265 24490 889231 979586 353257 172046 964221 209052 304766 512674 911460 13132 290488 54987 163286 688790 154986 507334 238753 106983 10 414179 876469 532484 778976 929901 943591 967171 469587 316333 244150 57922 229053 917338 511203 933812 821729 701430 296883 366202 767944 881775 779042 637856 431856 10 912289 273211 727244 973131 649991 777255 482888 941859 553495 697441 756292 418445 75572 770638 564931 184907 777394 947808 844799 76579 762209 622406 794276 875017 10 186510 943733 211495 577687 410184 715298 400377 819794 779170 661136 322632 109644 26953 124317 589387 993350 673656 983988 863474 14128 413613 638880 328456 938364 10 831657 632705 379672 709078 37977 336062 165991 174054 975371 579539 180438 578098 66805 455576 675288 761680 402764 82490 889866 31388 521076 292034 903500 400310 10 692919 900633 34333 972198 697650 49081 233120 805599 824351 230318 181523 824797 773679 85871 128484 580483 933857 685618 894061 992475 157281 748799 347483 751525 10 403726 545515 974442 785179 551996 489674 242989 66527 562029 966280 933934 874897 995219 144209 567298 830171 450266 474843 555109 493330 289088 86884 287847 648290 10 499902 902102 295608 773431 61251 520714 275555 122609 819854 806894 64717 83195 597092 430556 536392 147811 886412 335852 551396 918638 173654 729630 478563 118555 10 575980 230164 447550 546643 732089 98685 426115 72547 513479 225207 498197 602616 9670 399845 727473 947570 346311 330909 550601 121815 303455 264578 47816 775020 10 114449 28347 771013 794411 952791 605256 67925 529906 444753 267661 332848 196440 887980 271783 358214 692106 566661 934262 287913 414048 457619 667524 406732 537104 10 878766 330401 117497 76040 13349 889672 217041 107704 313388 715753 652322 9586 538248 420456 454699 49533 386493 746984 882659 169453 673721 544648 590094 985167 10 428496 490756 588842 885867 904828 534231 184395 640529 305319 783660 412683 677895 598354 296865 192220 687935 534546 221710 521110 939512 324016 642870 190774 264870 10 521025 37679 475869 590811 863850 138542 718189 800461 459651 826345 945835 295395 853530 930707 547026 44560 979589 549352 737635 416614 176940 209279 425711 215212 10 209289 699535 679583 518738 924974 803629 300856 984886 799998 50736 411817 805400 482372 778419 928609 783350 255426 866420 149823 876970 #include <iostream> #include <time.h> using namespace std; int oo = 2000000000; int T, n, xS, yS, xH, yH, point[11][2], vs[11]; long long result; int Abs(int a) { return (a < 0 ? -a : a); } void backtrack(int index, int x, int y, long long sum){ if(sum >= result) return; if(index == n){ int length = Abs(x - xH) + Abs(y - yH); if(sum + length < result) result = sum + length; return; } for(int choose = 0; choose < n; choose++){ if(!vs[choose]){ vs[choose]++; int length = Abs(x - point[choose][0]) + Abs(y - point[choose][1]); backtrack(index + 1, point[choose][0], point[choose][1], sum + length); vs[choose]--; } } } int main(){ freopen("input.txt", "r", stdin); // Calc clock clock_t time_start, time_end; time_start = clock(); cin >> T; for(int tc = 1; tc <= T; tc++){ // Initial && Input cin >> xS >> yS >> xH >> yH; cin >> n; for(int i = 0; i < n; i++){ cin >> point[i][0] >> point[i][1]; vs[i] = 0; } result = oo; // Solve Problem backtrack(0, xS, yS, 0); // Output cout << "Case #" << tc << " " << result << endl; } // Calc Time time_end = clock(); cout.setf(ios::fixed); cout.precision(5); cout << "Time: " << double (time_end - time_start) / double (CLOCKS_PER_SEC) << " s." << endl; return 0; }
Leave a Comment