Untitled
unknown
plain_text
10 months ago
6.9 kB
31
Indexable
Never
Tất cả vị trí trong vũ trụ được cho bởi tọa độ 2 chiều (X, Y). Tàu vũ trụ chỉ có thể di chuyển theo hướng song song với trục X hoặc trục Y và mất 1 giây để di chuyển khoảng cách 1 đơn vị. Do đó, thời gian mà tàu vũ trụ cần để di chuyển từ tọa độ (x1, y1) tới (x2, y2) được tính như sau: Có tất cả N hố đen trong không gian. Ki là thời gian để di chuyển qua mỗi hố đen, mỗi hố đen có Ki khác nhau. Và hố đen cho phép di chuyển theo 2 chiều. Để thuận tiện, 2 lối vào của hố đen được gọi là Cổng A và Cổng B. ※ Không bắt buộc phải sử dụng tất cả hố đen để di chuyển tới điểm đích. Cũng có thể không cần dùng đến bất kì hố đen nào trong quá trình di chuyển. Cũng không bắt buộc phải di chuyển qua hố đen mặc dù tàu vũ trụ gặp một cổng của hố đen đó. ▶ Cho thông tin về điểm bắt đầu và điểm đích (tọa độ) của tàu vũ trụ và thông tin về mỗi hố đen, hãy tìm thời gian ngắn nhất để di chuyển từ điểm bắt đầu tới điểm đích. [Giới hạn] 1. Số lượng hố đen N lớn hơn hoặc bằng 0 và nhỏ hơn hoặc bằng 5 (0 ≤ N ≤ 5). 2. Thời gian để di chuyển qua một hố đen Ki lớn hơn hoặc bằng 0 và nhỏ hơn hoặc bằng 3,000. (0 ≤ Ki ≤ 3,000) 3. X, Y, tọa độ trong vũ trụ lớn hơn hoặc bằng 0 và nhỏ hơn hoặc bằng 1,000. (0 ≤ X, Y ≤ 1,000) 4. Không có trường hợp nào mà tọa độ của điểm bắt đầu, điểm đích của tàu vũ trụ và tọa độ của những hố đen giống nhau. [Input] Dòng đầu tiên của là số lượng phép thử T. Từ dòng tiếp theo là thông tin về mỗi phép thử. Dòng đầu tiên của mỗi phép thử là số lượng hố đen N. Dòng thứ 2 là điểm bắt đầu [x1, y1] và điểm đích [x2, y2] của tàu vũ trụ. Từ dòng thứ 3 tới dòng thứ ‘N+1’ là thông tin về mỗi hố đen. Tọa độ [x, y] của Cổng A và [x, y] của Cổng B của mỗi hố đen, và thời gian để di chuyển qua hố đen. [Output] In “#T” cho phép thử thứ T, tiếp theo là một khoảng cách và in câu trả lời (T là số thứ tự của phép thử bắt đầu từ 1). 50 0 0 0 60 60 1 0 0 2 0 1 0 1 2 0 1 0 0 60 60 40 40 20 20 10 2 100 50 10 5 80 40 10 6 10 80 10 70 40 5 3 500 500 1000 1000 501 501 999 999 1000 1 1 499 499 100 1000 999 0 0 200 1 252 854 366 380 242 449 680 162 1259 2 59 382 300 172 138 782 647 631 2652 5 692 376 250 1778 2 367 327 15 769 458 876 184 906 2753 201 839 237 914 1319 2 349 891 539 609 745 98 995 52 211 819 578 556 643 958 3 234 844 255 803 487 718 343 942 1782 208 212 815 788 1383 55 665 111 67 2010 3 967 956 183 221 524 23 166 439 1103 165 695 160 159 1609 962 48 784 637 83 3 132 166 344 269 12 988 362 491 1616 334 451 460 52 937 274 814 695 725 1754 5 864 480 355 621 511 700 265 665 2108 56 778 760 899 778 748 184 469 260 340 87 99 187 794 214 485 721 6 833 1390 5 716 105 730 903 618 726 366 901 354 511 458 381 290 2760 709 339 608 935 2389 258 813 20 306 1786 751 925 300 36 809 4 427 186 957 6 418 546 129 68 991 717 531 219 739 511 335 696 872 404 2886 114 919 772 883 2139 1 276 721 686 539 345 126 755 149 2120 0 103 186 984 440 1 470 238 174 241 973 934 25 839 281 4 603 856 437 739 8 520 44 221 2391 647 653 202 16 2141 132 859 975 8 629 80 422 596 348 1226 3 122 269 280 23 715 854 968 103 550 130 625 219 762 1302 569 216 213 613 2292 4 119 870 322 958 265 632 990 182 1817 289 300 288 572 340 153 635 693 203 669 168 647 40 443 2517 1 854 395 198 415 706 331 272 19 2021 4 860 206 795 355 344 60 468 822 1047 833 545 968 44 2117 521 895 417 719 1968 72 730 772 547 2389 0 450 94 637 265 5 535 692 969 762 86 921 753 581 784 679 919 201 948 621 706 549 453 192 2854 604 358 664 855 2508 924 637 134 178 282 2 962 177 909 317 403 663 513 658 1342 32 674 610 596 2068 2 325 637 379 737 144 214 110 472 908 957 530 468 734 2260 5 328 263 278 446 129 146 237 907 2338 601 908 402 215 1638 902 165 435 912 1924 948 756 143 49 2021 122 239 765 870 2192 1 838 241 944 892 574 147 146 103 1997 0 804 211 578 557 1 125 738 836 951 332 421 833 970 333 4 62 168 552 21 913 595 642 568 528 340 773 50 550 1560 452 181 668 889 2761 802 209 588 773 915 3 646 858 276 204 917 104 333 317 1495 588 504 970 838 1007 510 507 495 282 2389 4 827 738 392 899 99 140 741 810 906 497 780 483 644 2602 252 312 299 793 235 181 498 354 95 1284 3 44 572 389 805 441 607 389 25 1364 416 846 995 115 2399 620 941 787 59 675 1 132 276 547 199 94 89 658 500 1906 3 145 135 450 976 823 984 383 11 1194 397 441 300 665 2185 334 166 944 440 2329 3 614 843 830 168 366 62 604 187 661 798 949 913 972 2822 940 412 939 615 411 3 462 754 117 71 598 359 173 121 581 860 839 402 676 55 216 737 899 880 595 2 548 853 541 860 84 89 282 752 1566 678 189 195 135 857 1 511 771 591 91 159 897 869 520 1669 1 983 868 785 307 5 641 275 950 814 3 86 313 245 464 578 193 315 525 1224 30 599 865 387 940 814 821 857 177 901 5 73 992 196 827 26 623 997 712 169 921 211 657 143 1137 576 633 291 679 2854 152 84 914 353 1973 255 425 831 443 1593 0 927 872 684 974 5 952 571 77 244 497 885 942 465 1752 609 388 790 316 208 1000 453 534 781 2925 565 662 684 9 2457 952 195 444 858 1627 5 465 529 681 23 884 321 605 227 1322 747 464 494 606 1833 840 735 144 613 477 434 981 8 882 2870 163 657 147 501 1027 5 549 313 923 775 97 893 868 423 2237 378 319 1 735 168 171 926 292 587 1878 705 500 749 739 1563 968 511 96 690 823 5 208 403 82 797 334 626 243 511 884 745 728 682 505 1699 779 303 717 187 2830 93 203 109 108 57 904 378 888 51 2624 5 21 961 161 658 339 38 140 315 1733 428 767 216 222 2386 563 725 204 496 1269 55 121 850 896 1197 145 323 504 105 662 #1 120 #2 2 #3 90 #4 41 #5 305 #6 588 #7 451 #8 794 #9 472 #10 62 #11 1519 #12 315 #13 650 #14 812 #15 710 #16 592 #17 1135 #18 299 #19 283 #20 404 #21 291 #22 676 #23 214 #24 358 #25 504 #26 193 #27 154 #28 233 #29 757 #30 572 #31 879 #32 637 #33 1024 #34 596 #35 578 #36 492 #37 1146 #38 891 #39 1028 #40 14 #41 760 #42 759 #43 310 #44 288 #45 345 #46 1202 #47 722 #48 836 #49 520 #50 443
Leave a Comment