HugoGiaohang

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;
 }