---------------------------------------------------------------------------------------------------- 10 0 3 5096 a 0 5 9765 a 1 0 1126 n 1 3 4204 n 1 5 3170 n 1 6 2985 a 2 8 5122 a 3 1 3138 n 3 8 2400 n 4 0 8724 a 4 1 5922 a 4 6 5115 a 4 8 7773 a 5 4 6402 a 5 7 4791 a 6 7 5224 a 7 8 5694 a 8 1 2809 n 8 2 3952 n 9 0 2168 a 9 2 5979 n 9 4 1233 n -1 +++ Original graph 0 -> 3 (5096, a) 5 (9765, a) 1 -> 0 (1126, n) 3 (4204, n) 5 (3170, n) 6 (2985, a) 2 -> 8 (5122, a) 3 -> 1 (3138, n) 8 (2400, n) 4 -> 0 (8724, a) 1 (5922, a) 6 (5115, a) 8 (7773, a) 5 -> 4 (6402, a) 7 (4791, a) 6 -> 7 (5224, a) 7 -> 8 (5694, a) 8 -> 1 (2809, n) 2 (3952, n) 9 -> 0 (2168, a) 2 (5979, n) 4 (1233, n) +++ AI subgraph 0 -> 3 (5096, a) 5 (9765, a) 1 -> 6 (2985, a) 2 -> 8 (5122, a) 3 -> 4 -> 0 (8724, a) 1 (5922, a) 6 (5115, a) 8 (7773, a) 5 -> 4 (6402, a) 7 (4791, a) 6 -> 7 (5224, a) 7 -> 8 (5694, a) 8 -> 9 -> 0 (2168, a) +++ Cheapest AI prices 0 1 2 3 4 5 6 7 8 9 0 -> 0 22089 - 5096 16167 9765 21282 14556 20250 - 1 -> - 0 - - - - 2985 8209 13903 - 2 -> - - 0 - - - - - 5122 - 3 -> - - - 0 - - - - - - 4 -> 8724 5922 - 13820 0 18489 5115 10339 7773 - 5 -> 15126 12324 - 20222 6402 0 11517 4791 10485 - 6 -> - - - - - - 0 5224 10918 - 7 -> - - - - - - - 0 5694 - 8 -> - - - - - - - - 0 - 9 -> 2168 24257 - 7264 18335 11933 23450 16724 22418 0 +++ Cheapest prices with at most one non-AI leg 0 1 2 3 4 5 6 7 8 9 0 -> 0 22089 24202 5096 16167 9765 21282 14556 20250 - 1 -> 1126 0 17855 4204 9572 3170 2985 8209 13903 - 2 -> - 7931 0 - - - 10916 16140 5122 - 3 -> - 3138 - 0 - - 6123 11347 2400 - 4 -> 8724 5922 11725 13820 0 18489 5115 10339 7773 - 5 -> 15126 12324 14437 20222 6402 0 11517 4791 10485 - 6 -> - 13727 14870 - - - 0 5224 10918 - 7 -> - 8503 9646 - - - 11488 0 5694 - 8 -> - 2809 3952 - - - 5794 11018 0 - 9 -> 2168 24257 5979 7264 18335 11933 23450 16724 22418 0 +++ Cheapest prices with any number of non-AI legs 0 1 2 3 4 5 6 7 8 9 0 -> 0 22089 11448 5096 16167 9765 21282 14556 20250 - 1 -> 1126 0 10556 4204 9572 3170 2985 8209 13903 - 2 -> 9057 7931 0 12135 17503 11101 10916 15892 5122 - 3 -> 4264 3138 6352 0 12710 6308 6123 11099 2400 - 4 -> 8724 5922 11725 13820 0 18489 5115 10339 7773 - 5 -> 15126 12324 14437 20222 6402 0 11517 4791 10485 - 6 -> 14853 13727 14870 17931 23299 16897 0 5224 10918 - 7 -> 9629 8503 9646 12707 18075 11673 11488 0 5694 - 8 -> 3935 2809 3952 7013 12381 5979 5794 10770 0 - 9 -> 2168 24257 5979 7264 18335 11933 23450 16724 22418 0 ---------------------------------------------------------------------------------------------------- 15 0 1 5680 a 0 7 8736 n 0 9 2492 n 0 10 8372 a 1 6 8898 a 2 12 3346 a 3 13 5768 a 4 0 7398 a 4 9 9215 a 4 10 7962 n 4 14 2678 a 5 0 3580 a 5 6 4745 n 5 7 2776 n 5 12 2025 a 6 3 8958 n 6 7 3384 n 6 9 8247 n 7 4 2617 a 7 8 4210 a 8 2 6110 n 8 9 8000 a 8 12 7555 n 8 14 8429 a 9 0 2639 n 9 2 7169 n 10 6 9401 n 10 14 1990 n 11 0 9370 a 11 8 7612 a 11 14 1425 n 12 1 1620 a 12 7 1663 a 12 8 1430 a 12 9 1211 n 13 1 9871 a 13 6 5681 a 13 10 3396 n 13 11 3057 a 13 12 2088 a 14 5 8696 n 14 9 7894 n 14 10 5860 n 14 11 1797 a -1 +++ Original graph 0 -> 1 (5680, a) 7 (8736, n) 9 (2492, n) 10 (8372, a) 1 -> 6 (8898, a) 2 -> 12 (3346, a) 3 -> 13 (5768, a) 4 -> 0 (7398, a) 9 (9215, a) 10 (7962, n) 14 (2678, a) 5 -> 0 (3580, a) 6 (4745, n) 7 (2776, n) 12 (2025, a) 6 -> 3 (8958, n) 7 (3384, n) 9 (8247, n) 7 -> 4 (2617, a) 8 (4210, a) 8 -> 2 (6110, n) 9 (8000, a) 12 (7555, n) 14 (8429, a) 9 -> 0 (2639, n) 2 (7169, n) 10 -> 6 (9401, n) 14 (1990, n) 11 -> 0 (9370, a) 8 (7612, a) 14 (1425, n) 12 -> 1 (1620, a) 7 (1663, a) 8 (1430, a) 9 (1211, n) 13 -> 1 (9871, a) 6 (5681, a) 10 (3396, n) 11 (3057, a) 12 (2088, a) 14 -> 5 (8696, n) 9 (7894, n) 10 (5860, n) 11 (1797, a) +++ AI subgraph 0 -> 1 (5680, a) 10 (8372, a) 1 -> 6 (8898, a) 2 -> 12 (3346, a) 3 -> 13 (5768, a) 4 -> 0 (7398, a) 9 (9215, a) 14 (2678, a) 5 -> 0 (3580, a) 12 (2025, a) 6 -> 7 -> 4 (2617, a) 8 (4210, a) 8 -> 9 (8000, a) 14 (8429, a) 9 -> 10 -> 11 -> 0 (9370, a) 8 (7612, a) 12 -> 1 (1620, a) 7 (1663, a) 8 (1430, a) 13 -> 1 (9871, a) 6 (5681, a) 11 (3057, a) 12 (2088, a) 14 -> 11 (1797, a) +++ Cheapest AI prices 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 -> 0 5680 - - - - 14578 - - - 8372 - - - - 1 -> - 0 - - - - 8898 - - - - - - - - 2 -> 15024 4966 0 - 7626 - 13864 5009 4776 12776 23396 12101 3346 - 10304 3 -> 18195 9476 - 0 12136 - 11449 9519 9286 17286 26567 8825 7856 5768 14814 4 -> 7398 13078 - - 0 - 21976 - 12087 9215 15770 4475 - - 2678 5 -> 3580 3645 - - 6305 0 12543 3688 3455 11455 11952 10780 2025 - 8983 6 -> - - - - - - 0 - - - - - - - - 7 -> 10015 15695 - - 2617 - 24593 0 4210 11832 18387 7092 - - 5295 8 -> 19596 25276 - - - - 34174 - 0 8000 27968 10226 - - 8429 9 -> - - - - - - - - - 0 - - - - - 10 -> - - - - - - - - - - 0 - - - - 11 -> 9370 15050 - - - - 23948 - 7612 15612 17742 0 - - 16041 12 -> 11678 1620 - - 4280 - 10518 1663 1430 9430 20050 8755 0 - 6958 13 -> 12427 3708 - - 6368 - 5681 3751 3518 11518 20799 3057 2088 0 9046 14 -> 11167 16847 - - - - 25745 - 9409 17409 19539 1797 - - 0 +++ Cheapest prices with at most one non-AI leg 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 -> 0 5680 - 23536 11353 - 14578 8736 12946 2492 8372 12159 31392 29304 10362 1 -> 22297 0 - 17856 14899 - 8898 12282 16492 17145 30669 19374 25712 23624 17577 2 -> 15024 4966 0 22822 7626 19000 13864 5009 4776 12776 23396 12101 3346 28590 10304 3 -> 18195 9476 15396 0 12136 23510 11449 9519 9286 17286 26567 8825 7856 5768 14814 4 -> 7398 13078 16384 30934 0 11374 21976 15062 12087 9215 15770 4475 13399 36702 2678 5 -> 3580 3645 9565 21501 6305 0 12543 3688 3455 11455 11952 10780 2025 27269 8983 6 -> 13399 18434 - 8958 6001 - 0 3384 7594 8247 21771 10476 16814 14726 8679 7 -> 10015 15695 10320 33551 2617 13991 24593 0 4210 11832 18387 7092 11765 39319 5295 8 -> 19596 25276 6110 43132 11835 17125 34174 9218 0 8000 27968 10226 7555 48900 8429 9 -> 2639 8319 7169 - 14795 - 17217 12178 11945 0 11011 19270 10515 - 17473 10 -> 13157 18837 - - - - 9401 - 11399 19399 0 3787 - - 1990 11 -> 9370 15050 13722 32906 19447 24737 23948 16830 7612 15612 17742 0 15167 38674 16041 12 -> 11678 1620 7540 19476 4280 15654 10518 1663 1430 9430 20050 8755 0 25244 6958 13 -> 12427 3708 9628 14639 6368 17742 5681 3751 3518 11518 20799 3057 2088 0 9046 14 -> 11167 16847 15519 34703 15001 8696 25745 12384 9409 17409 19539 1797 10721 40471 0 +++ Cheapest prices with any number of non-AI legs 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 -> 0 5680 9661 23536 11353 19058 14578 8736 12946 2492 8372 12159 13007 29304 10362 1 -> 19784 0 22602 17856 14899 26273 8898 12282 16492 17145 22861 19374 24047 23624 17577 2 -> 15024 4966 0 22822 7626 19000 13864 5009 4776 12776 23396 12101 3346 28590 10304 3 -> 18195 9476 15396 0 12136 18946 11449 9519 9286 17286 26567 8825 7856 5768 14814 4 -> 7398 13078 16384 25077 0 11374 21976 14150 12087 9215 15770 4475 13399 30845 2678 5 -> 3580 3645 9565 13703 6305 0 12543 3688 3455 11455 11952 10780 2025 19471 8983 6 -> 10886 16566 13704 8958 6001 17375 0 3384 7594 8247 13963 10476 15149 14726 8679 7 -> 10015 15695 10320 27694 2617 13991 24593 0 4210 11832 18387 7092 11765 33462 5295 8 -> 19596 25276 6110 27031 11835 17125 34174 9218 0 8000 27968 10226 7555 32799 8429 9 -> 2639 8319 7169 26175 13992 21697 17217 11375 11945 0 11011 14798 10515 31943 13001 10 -> 12523 14331 17053 18359 15402 10686 9401 12785 11399 9884 0 3787 12711 24127 1990 11 -> 9370 15050 13722 23824 15514 10121 23948 12897 7612 15612 17742 0 12146 29592 16041 12 -> 11678 1620 7540 19476 4280 15654 10518 1663 1430 9430 20050 8755 0 25244 6958 13 -> 12427 3708 9628 14639 6368 13178 5681 3751 3518 11518 20799 3057 2088 0 9046 14 -> 11167 16847 15063 22399 14089 8696 25745 11472 9409 17409 19539 1797 10721 28167 0 ---------------------------------------------------------------------------------------------------- 20 0 3 5116 n 0 4 6920 a 0 8 7913 a 0 12 7470 a 1 2 3787 a 1 5 7793 n 1 6 2065 a 1 17 4895 n 2 0 1163 n 2 3 4787 a 2 4 7464 a 2 5 2609 a 2 10 6962 n 2 12 6409 n 2 15 2092 a 2 16 6359 n 3 1 7434 a 3 2 6341 a 3 7 5997 a 3 8 9311 n 3 10 6015 a 3 13 1742 n 3 16 4638 n 4 2 8150 n 4 11 8190 n 4 15 4961 n 5 6 8316 n 5 7 3818 n 5 17 5628 n 5 19 2425 n 6 3 3982 a 6 12 5732 n 6 14 8939 a 6 16 8551 n 6 18 3188 a 6 19 4613 a 7 2 9868 n 7 4 8935 a 7 10 6093 a 8 19 5011 n 9 3 2823 n 9 10 4889 n 9 11 8717 n 9 14 9611 n 9 19 2929 n 10 19 1764 n 11 4 1478 a 11 5 3407 a 11 9 6822 a 11 15 9021 a 12 1 8181 n 12 4 1118 n 12 7 6670 n 12 11 7714 n 12 15 9970 n 12 17 5303 a 13 2 8603 n 13 3 5035 a 14 4 9127 a 14 5 9935 n 14 6 8538 n 14 7 9926 a 14 8 1872 n 14 9 5841 n 14 11 4943 a 14 12 8160 a 14 15 6594 n 15 5 7634 a 16 4 8648 a 16 9 4327 n 16 11 7754 n 16 14 2584 n 17 6 2719 n 18 1 9231 a 18 10 6204 a 18 14 5373 n 19 1 4632 a 19 6 1365 a 19 10 3869 n -1 +++ Original graph 0 -> 3 (5116, n) 4 (6920, a) 8 (7913, a) 12 (7470, a) 1 -> 2 (3787, a) 5 (7793, n) 6 (2065, a) 17 (4895, n) 2 -> 0 (1163, n) 3 (4787, a) 4 (7464, a) 5 (2609, a) 10 (6962, n) 12 (6409, n) 15 (2092, a) 16 (6359, n) 3 -> 1 (7434, a) 2 (6341, a) 7 (5997, a) 8 (9311, n) 10 (6015, a) 13 (1742, n) 16 (4638, n) 4 -> 2 (8150, n) 11 (8190, n) 15 (4961, n) 5 -> 6 (8316, n) 7 (3818, n) 17 (5628, n) 19 (2425, n) 6 -> 3 (3982, a) 12 (5732, n) 14 (8939, a) 16 (8551, n) 18 (3188, a) 19 (4613, a) 7 -> 2 (9868, n) 4 (8935, a) 10 (6093, a) 8 -> 19 (5011, n) 9 -> 3 (2823, n) 10 (4889, n) 11 (8717, n) 14 (9611, n) 19 (2929, n) 10 -> 19 (1764, n) 11 -> 4 (1478, a) 5 (3407, a) 9 (6822, a) 15 (9021, a) 12 -> 1 (8181, n) 4 (1118, n) 7 (6670, n) 11 (7714, n) 15 (9970, n) 17 (5303, a) 13 -> 2 (8603, n) 3 (5035, a) 14 -> 4 (9127, a) 5 (9935, n) 6 (8538, n) 7 (9926, a) 8 (1872, n) 9 (5841, n) 11 (4943, a) 12 (8160, a) 15 (6594, n) 15 -> 5 (7634, a) 16 -> 4 (8648, a) 9 (4327, n) 11 (7754, n) 14 (2584, n) 17 -> 6 (2719, n) 18 -> 1 (9231, a) 10 (6204, a) 14 (5373, n) 19 -> 1 (4632, a) 6 (1365, a) 10 (3869, n) +++ AI subgraph 0 -> 4 (6920, a) 8 (7913, a) 12 (7470, a) 1 -> 2 (3787, a) 6 (2065, a) 2 -> 3 (4787, a) 4 (7464, a) 5 (2609, a) 15 (2092, a) 3 -> 1 (7434, a) 2 (6341, a) 7 (5997, a) 10 (6015, a) 4 -> 5 -> 6 -> 3 (3982, a) 14 (8939, a) 18 (3188, a) 19 (4613, a) 7 -> 4 (8935, a) 10 (6093, a) 8 -> 9 -> 10 -> 11 -> 4 (1478, a) 5 (3407, a) 9 (6822, a) 15 (9021, a) 12 -> 17 (5303, a) 13 -> 3 (5035, a) 14 -> 4 (9127, a) 7 (9926, a) 11 (4943, a) 12 (8160, a) 15 -> 5 (7634, a) 16 -> 4 (8648, a) 17 -> 18 -> 1 (9231, a) 10 (6204, a) 19 -> 1 (4632, a) 6 (1365, a) +++ Cheapest AI prices 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 0 -> 0 - - - 6920 - - - 7913 - - - 7470 - - - - 12773 - - 1 -> - 0 3787 6047 11251 6396 2065 12044 - 22769 11457 15947 19164 - 11004 5879 - 24467 5253 6678 2 -> - 12221 0 4787 7464 2609 14286 10784 - 34990 10802 28168 31385 - 23225 2092 - 36688 17474 18899 3 -> - 7434 6341 0 13805 8950 9499 5997 - 30203 6015 23381 26598 - 18438 8433 - 31901 12687 14112 4 -> - - - - 0 - - - - - - - - - - - - - - - 5 -> - - - - - 0 - - - - - - - - - - - - - - 6 -> - 9245 10323 3982 15360 12932 0 9979 - 20704 9392 13882 17099 - 8939 12415 - 22402 3188 4613 7 -> - - - - 8935 - - 0 - - 6093 - - - - - - - - - 8 -> - - - - - - - - 0 - - - - - - - - - - - 9 -> - - - - - - - - - 0 - - - - - - - - - - 10 -> - - - - - - - - - - 0 - - - - - - - - - 11 -> - - - - 1478 3407 - - - 6822 - 0 - - - 9021 - - - - 12 -> - - - - - - - - - - - - 0 - - - - 5303 - - 13 -> - 12469 11376 5035 18840 13985 14534 11032 - 35238 11050 28416 31633 0 23473 13468 - 36936 17722 19147 14 -> - - - - 6421 8350 - 9926 - 11765 16019 4943 8160 - 0 13964 - 13463 - - 15 -> - - - - - 7634 - - - - - - - - - 0 - - - - 16 -> - - - - 8648 - - - - - - - - - - - 0 - - - 17 -> - - - - - - - - - - - - - - - - - 0 - - 18 -> - 9231 13018 15278 20482 15627 11296 21275 - 32000 6204 25178 28395 - 20235 15110 - 33698 0 15909 19 -> - 4632 8419 5347 15883 11028 1365 11344 - 22069 10757 15247 18464 - 10304 10511 - 23767 4553 0 +++ Cheapest prices with at most one non-AI leg 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 0 -> 0 12550 11457 5116 6920 14066 14289 11113 7913 21932 11131 15110 7470 - 23228 11881 - 12773 17477 12924 1 -> 4950 0 3787 6047 11251 6396 2065 12044 12863 22769 11457 15947 19164 7789 11004 5879 10146 24467 5253 6678 2 -> 1163 12221 0 4787 7464 2609 14286 10784 9076 34990 10802 28168 31385 6529 23225 2092 6359 36688 17474 18899 3 -> 7504 7434 6341 0 13805 8950 9499 5997 9311 30203 6015 23381 26598 1742 18438 8433 4638 31901 12687 14112 4 -> - 20371 8150 12937 0 10759 22436 18934 - 15012 18952 8190 39535 - 31375 4961 - 44838 25624 27049 5 -> - 7057 10844 7772 12753 0 3790 3818 - 24494 9911 17672 20889 - 12729 12936 - 5628 6978 2425 6 -> 11486 9245 10323 3982 15360 12932 0 9979 10811 20704 9392 13882 17099 5724 8939 12415 8551 22402 3188 4613 7 -> - 12489 9868 13204 8935 12477 9222 0 - 23947 6093 17125 26321 - 18161 11960 - 31624 12410 7857 8 -> - 9643 13430 10358 20894 16039 6376 16355 0 27080 15768 20258 23475 - 15315 15522 - 28778 9564 5011 9 -> - 7561 9164 2823 10195 11773 4294 8820 - 0 4889 8717 17771 - 9611 11256 - 23074 7482 2929 10 -> - 6396 10183 7111 17647 12792 3129 13108 - 23833 0 17011 20228 - 12068 12275 - 25531 6317 1764 11 -> - 10464 9628 9645 1478 3407 7197 7225 - 6822 11711 0 24296 - 16136 9021 - 9035 10385 5832 12 -> - 8181 11968 12004 1118 11121 8022 6670 - 14536 12763 7714 0 - 16961 9970 - 5303 11210 12635 13 -> 12539 12469 11376 5035 18840 13985 14534 11032 14346 35238 11050 28416 31633 0 23473 13468 9673 36936 17722 19147 14 -> - 15407 14571 12520 6421 8350 8538 9926 1872 11765 16019 4943 8160 - 0 13964 - 13463 11726 10775 15 -> - 14691 18478 15406 20387 7634 11424 11452 - 32128 17545 25306 28523 - 20363 0 - 13262 14612 10059 16 -> - 29019 16798 21585 8648 10934 31084 12510 - 4327 18603 7527 10744 - 2584 13609 0 16047 34272 35697 17 -> - 11964 13042 6701 18079 15651 2719 12698 - 23423 12111 16601 19818 - 11658 15134 - 0 5907 7332 18 -> 14181 9231 13018 15278 20482 15627 11296 21275 22094 32000 6204 25178 28395 17020 20235 15110 19377 33698 0 15909 19 -> 9582 4632 8419 5347 15883 11028 1365 11344 12176 22069 10757 15247 18464 7089 10304 10511 9916 23767 4553 0 +++ Cheapest prices with any number of non-AI legs 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 0 -> 0 12550 11457 5116 6920 14066 14260 11113 7913 14081 11131 15110 7470 6858 12338 11881 9754 12773 17448 12895 1 -> 4950 0 3787 6047 11251 6396 2065 12044 12498 22769 11457 15947 19164 7789 11004 5879 10146 24467 5253 6678 2 -> 1163 12221 0 4787 7464 2609 14286 10784 9076 34990 10802 28168 31385 6529 23225 2092 6359 36688 17474 18899 3 -> 7504 7434 6341 0 13805 8950 9499 5997 9094 30203 6015 23381 26598 1742 18438 8433 4638 31901 12687 14112 4 -> 9313 17816 8150 12937 0 10759 14549 14577 17226 15012 15112 8190 14559 14679 17093 4961 14509 16387 17737 13184 5 -> 12007 7057 10844 7772 10640 0 3790 3818 14223 16668 6294 17236 9522 9514 12351 12936 12341 5628 6978 2425 6 -> 11486 9245 10323 3982 15360 12932 0 9979 10433 20704 9392 13882 17099 5724 8939 12415 8551 22402 3188 4613 7 -> 11031 12489 9868 13204 8935 12477 9222 0 18944 20554 6093 17125 14954 14946 17783 11960 16227 17384 12410 7857 8 -> 14593 9643 13430 10358 13226 16039 6376 16355 0 19254 8880 19822 12108 12100 14937 15522 14927 14538 9564 5011 9 -> 10327 7561 9164 2823 10195 11773 4294 8820 11483 0 4889 8717 10026 4565 9611 11256 7461 12456 7482 2929 10 -> 11346 6396 10183 7111 9979 12792 3129 13108 13562 16007 0 16575 8861 8853 11690 12275 11680 11291 6317 1764 11 -> 10791 10464 9628 9645 1478 3407 7197 7225 17630 6822 9701 0 12929 11387 15758 9021 14283 9035 10385 5832 12 -> 10431 8181 9268 12004 1118 11121 8022 6670 18344 14536 12763 7714 0 13746 16583 6079 15627 5303 11210 12635 13 -> 9766 12469 11376 5035 18840 13985 14534 11032 14129 35238 11050 28416 31633 0 23473 13468 9673 36936 17722 19147 14 -> 15734 11515 14571 8664 6421 8350 8248 9926 1872 11765 16019 4943 8160 10406 0 13964 13302 13463 11436 6883 15 -> 19641 14691 18478 15406 18274 7634 11424 11452 21857 24302 13928 24870 17156 17148 19985 0 19975 13262 14612 10059 16 -> 14654 11888 13491 7150 8648 10934 8621 12510 4456 4327 9216 7527 10744 8892 2584 9178 0 16047 11809 7256 17 -> 14205 11964 13042 6701 9569 15651 2719 12698 13152 15597 11201 16165 8451 8443 11280 14530 11270 0 5907 7332 18 -> 14181 9231 13018 15278 20482 15627 11296 21275 7245 32000 6204 25178 28395 15057 20235 15110 17884 33698 0 15909 19 -> 9582 4632 8419 5347 15883 11028 1365 11344 11798 22069 10757 15247 18464 7089 10304 10511 9916 23767 4553 0 ---------------------------------------------------------------------------------------------------- 25 0 14 3668 n 0 18 7143 a 0 19 4921 a 1 2 5256 a 1 5 6259 a 1 6 2053 n 1 11 2893 n 1 22 3742 a 1 23 5350 n 2 1 1147 a 2 3 8552 a 2 6 4186 a 2 11 5526 n 2 17 3106 a 2 18 7456 a 2 22 9049 n 3 1 4750 a 3 6 7294 a 3 10 6998 a 3 13 2490 a 4 3 7463 n 4 7 5211 n 4 9 1506 n 4 10 9740 a 4 11 4743 a 4 20 3800 n 5 0 2873 a 5 4 3979 n 5 15 4023 a 5 21 5096 n 5 22 2279 n 6 4 2029 a 6 17 8358 a 6 24 9683 a 7 5 2045 a 7 8 7084 a 7 11 9564 a 7 15 2962 a 7 17 9055 a 7 18 1777 a 8 1 5518 n 8 2 2602 a 8 3 4182 a 8 7 9859 n 8 16 7146 n 8 20 1668 a 8 21 6187 a 9 5 5483 a 9 7 4246 n 9 11 1799 n 9 14 8918 n 9 15 6939 a 9 17 3235 n 9 21 2269 a 10 0 9747 a 10 15 5897 n 10 16 8133 n 10 22 4971 n 11 4 9545 a 11 6 2740 a 11 9 7902 a 11 15 9499 a 11 17 2588 n 11 20 8188 n 11 24 5921 n 12 4 1552 a 12 6 9611 a 12 13 2587 a 12 24 9250 n 13 1 6726 n 13 9 4973 n 13 15 2892 a 13 20 4089 a 14 3 6385 a 14 9 3024 a 14 18 7629 a 14 24 5741 a 15 2 2109 a 15 3 5515 n 15 8 5717 a 15 20 3926 n 15 22 6786 a 15 23 1085 a 16 9 6092 n 17 9 5490 n 17 10 5776 a 17 15 8413 a 17 19 6182 n 17 20 6274 n 17 22 1887 n 17 24 9035 n 18 2 7667 n 18 3 3443 a 18 5 5249 a 18 6 1015 n 18 10 2282 a 18 12 5445 a 19 12 2051 a 19 17 2355 a 20 1 1726 a 20 10 1306 n 20 12 3047 a 20 14 6637 n 20 23 6908 n 21 0 1744 n 21 13 7162 a 21 19 5513 n 22 0 3944 a 22 1 8198 n 22 11 6366 a 22 19 9431 n 23 2 4352 n 23 3 4551 n 23 14 6714 n 24 10 7919 n 24 12 9179 n 24 13 9870 n 24 18 9517 a 24 19 6803 a -1 +++ Original graph 0 -> 14 (3668, n) 18 (7143, a) 19 (4921, a) 1 -> 2 (5256, a) 5 (6259, a) 6 (2053, n) 11 (2893, n) 22 (3742, a) 23 (5350, n) 2 -> 1 (1147, a) 3 (8552, a) 6 (4186, a) 11 (5526, n) 17 (3106, a) 18 (7456, a) 22 (9049, n) 3 -> 1 (4750, a) 6 (7294, a) 10 (6998, a) 13 (2490, a) 4 -> 3 (7463, n) 7 (5211, n) 9 (1506, n) 10 (9740, a) 11 (4743, a) 20 (3800, n) 5 -> 0 (2873, a) 4 (3979, n) 15 (4023, a) 21 (5096, n) 22 (2279, n) 6 -> 4 (2029, a) 17 (8358, a) 24 (9683, a) 7 -> 5 (2045, a) 8 (7084, a) 11 (9564, a) 15 (2962, a) 17 (9055, a) 18 (1777, a) 8 -> 1 (5518, n) 2 (2602, a) 3 (4182, a) 7 (9859, n) 16 (7146, n) 20 (1668, a) 21 (6187, a) 9 -> 5 (5483, a) 7 (4246, n) 11 (1799, n) 14 (8918, n) 15 (6939, a) 17 (3235, n) 21 (2269, a) 10 -> 0 (9747, a) 15 (5897, n) 16 (8133, n) 22 (4971, n) 11 -> 4 (9545, a) 6 (2740, a) 9 (7902, a) 15 (9499, a) 17 (2588, n) 20 (8188, n) 24 (5921, n) 12 -> 4 (1552, a) 6 (9611, a) 13 (2587, a) 24 (9250, n) 13 -> 1 (6726, n) 9 (4973, n) 15 (2892, a) 20 (4089, a) 14 -> 3 (6385, a) 9 (3024, a) 18 (7629, a) 24 (5741, a) 15 -> 2 (2109, a) 3 (5515, n) 8 (5717, a) 20 (3926, n) 22 (6786, a) 23 (1085, a) 16 -> 9 (6092, n) 17 -> 9 (5490, n) 10 (5776, a) 15 (8413, a) 19 (6182, n) 20 (6274, n) 22 (1887, n) 24 (9035, n) 18 -> 2 (7667, n) 3 (3443, a) 5 (5249, a) 6 (1015, n) 10 (2282, a) 12 (5445, a) 19 -> 12 (2051, a) 17 (2355, a) 20 -> 1 (1726, a) 10 (1306, n) 12 (3047, a) 14 (6637, n) 23 (6908, n) 21 -> 0 (1744, n) 13 (7162, a) 19 (5513, n) 22 -> 0 (3944, a) 1 (8198, n) 11 (6366, a) 19 (9431, n) 23 -> 2 (4352, n) 3 (4551, n) 14 (6714, n) 24 -> 10 (7919, n) 12 (9179, n) 13 (9870, n) 18 (9517, a) 19 (6803, a) +++ AI subgraph 0 -> 18 (7143, a) 19 (4921, a) 1 -> 2 (5256, a) 5 (6259, a) 22 (3742, a) 2 -> 1 (1147, a) 3 (8552, a) 6 (4186, a) 17 (3106, a) 18 (7456, a) 3 -> 1 (4750, a) 6 (7294, a) 10 (6998, a) 13 (2490, a) 4 -> 10 (9740, a) 11 (4743, a) 5 -> 0 (2873, a) 15 (4023, a) 6 -> 4 (2029, a) 17 (8358, a) 24 (9683, a) 7 -> 5 (2045, a) 8 (7084, a) 11 (9564, a) 15 (2962, a) 17 (9055, a) 18 (1777, a) 8 -> 2 (2602, a) 3 (4182, a) 20 (1668, a) 21 (6187, a) 9 -> 5 (5483, a) 15 (6939, a) 21 (2269, a) 10 -> 0 (9747, a) 11 -> 4 (9545, a) 6 (2740, a) 9 (7902, a) 15 (9499, a) 12 -> 4 (1552, a) 6 (9611, a) 13 (2587, a) 13 -> 15 (2892, a) 20 (4089, a) 14 -> 3 (6385, a) 9 (3024, a) 18 (7629, a) 24 (5741, a) 15 -> 2 (2109, a) 8 (5717, a) 22 (6786, a) 23 (1085, a) 16 -> 17 -> 10 (5776, a) 15 (8413, a) 18 -> 3 (3443, a) 5 (5249, a) 10 (2282, a) 12 (5445, a) 19 -> 12 (2051, a) 17 (2355, a) 20 -> 1 (1726, a) 12 (3047, a) 21 -> 13 (7162, a) 22 -> 0 (3944, a) 11 (6366, a) 23 -> 24 -> 18 (9517, a) 19 (6803, a) +++ Cheapest AI prices 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 0 -> 0 15336 14560 10586 8524 12392 16007 - 18168 21169 9425 13267 6972 9559 - 12451 - 7276 7143 4921 13648 23438 19078 13536 25690 1 -> 7686 0 5256 13808 11471 6259 9442 - 15999 18010 14138 10108 14658 16298 - 10282 - 8362 12712 12607 17667 20279 3742 11367 19125 2 -> 8833 1147 0 8552 6215 7406 4186 - 17146 18860 8882 10958 12901 11042 - 11429 - 3106 7456 13754 15131 21129 4889 12514 13869 3 -> 12436 4750 7491 0 9323 11009 7294 - 11099 21968 6998 14066 9626 2490 - 5382 - 10597 14947 17357 6579 17286 8492 6467 16977 4 -> 19487 17498 16351 24141 0 18128 7483 - 19959 12645 9740 4743 24674 22076 - 14242 - 15841 23807 23969 21627 14914 21028 15327 17166 5 -> 2873 7279 6132 13459 11397 0 10318 - 9740 24042 12298 16140 9845 12432 - 4023 - 9238 10016 7794 11408 15927 10809 5108 20001 6 -> 21516 19527 18380 22643 2029 20157 0 - 21988 14674 11769 6772 18537 21124 - 16271 - 8358 19200 16486 23656 16943 23057 17356 9683 7 -> 4918 6218 5071 5220 8774 2045 9257 0 7084 17466 4059 9564 7222 7710 - 2962 - 8177 1777 9839 8752 13271 9748 4047 18940 8 -> 11080 3394 2602 4182 6267 9653 6788 - 0 18912 11180 11010 4715 6672 - 9564 - 5708 10058 16001 1668 6187 7136 10649 16471 9 -> 8356 10195 9048 16838 15263 5483 13234 - 12656 0 17781 20006 15328 9431 - 6939 - 12154 15499 13277 13520 2269 13725 8024 22917 10 -> 9747 25083 24307 20333 18271 22139 25754 - 27915 30916 0 23014 16719 19306 - 22198 - 17023 16890 14668 23395 33185 28825 23283 35437 11 -> 16258 12755 11608 19398 4769 13385 2740 - 15216 7902 14509 0 19931 17333 - 9499 - 11098 19064 19226 16884 10171 16285 10584 12423 12 -> 16088 8402 7588 15378 1552 14661 9035 - 11196 14197 11292 6295 0 2587 - 5479 - 10694 15044 21009 6676 16466 12144 6564 18718 13 -> 13501 5815 5001 12791 8688 12074 9187 - 8609 21333 13883 13431 7136 0 - 2892 - 8107 12457 18422 4089 14796 9557 3977 18870 14 -> 11380 11135 12072 6385 14626 8507 13679 - 15680 3024 9911 19369 13074 8875 0 9963 - 14899 7629 12544 12964 5293 14877 11048 5741 15 -> 10730 3256 2109 9899 8324 9515 6295 - 5717 20969 10991 13067 10432 12389 - 0 - 5215 9565 15651 7385 11904 6786 1085 15978 16 -> - - - - - - - - - - - - - - - - 0 - - - - - - - - 17 -> 15523 11669 10522 18312 16737 17928 14708 - 14130 29382 5776 21480 18845 20802 - 8413 - 0 17978 20444 15798 20317 15199 9498 24391 18 -> 8122 8193 10934 3443 6997 5249 10737 - 14542 19642 2282 11740 5445 5933 - 8825 - 14040 0 13043 10022 20729 11935 9910 20420 19 -> 17878 10453 9639 17429 3603 16712 11086 - 13247 16248 8131 8346 2051 4638 - 7530 - 2355 17095 0 8727 18517 14195 8615 20769 20 -> 9412 1726 6982 15534 4599 7985 11168 - 14243 17244 14339 9342 3047 5634 - 8526 - 10088 14438 14333 0 19513 5468 9611 20851 21 -> 20663 12977 12163 19953 15850 19236 16349 - 15771 28495 21045 20593 14298 7162 - 10054 - 15269 19619 25584 11251 0 16719 11139 26032 22 -> 3944 19121 17974 14530 11135 16336 9106 - 21582 14268 13369 6366 10916 13503 - 15865 - 11220 11087 8865 17592 16537 0 16950 18789 23 -> - - - - - - - - - - - - - - - - - - - - - - - 0 - 24 -> 17639 17256 16442 12960 10406 14766 17889 - 20050 23051 11799 15149 8854 11441 - 14333 - 9158 9517 6803 15530 25320 20998 15418 0 +++ Cheapest prices with at most one non-AI leg 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 0 -> 0 15336 14560 10586 8524 12392 16007 13735 18168 21169 9425 13267 6972 9559 3668 12451 17558 7276 7143 4921 13648 23438 19078 13536 25690 1 -> 7686 0 5256 13808 11471 6259 9442 16682 15999 18010 14138 10108 14658 16298 11354 10282 22271 8362 12712 12607 17667 20279 3742 11367 19125 2 -> 8833 1147 0 8552 6215 7406 4186 11426 17146 18860 8882 10958 12901 11042 12501 11429 17015 3106 7456 13754 15131 21129 4889 12514 13869 3 -> 12436 4750 7491 0 9323 11009 7294 14534 11099 21968 6998 14066 9626 2490 13181 5382 15131 10597 14947 17357 6579 17286 8492 6467 16977 4 -> 19487 17498 16351 24141 0 18128 7483 5211 19959 12645 9740 4743 24674 22076 21563 14242 17873 15841 23807 23969 21627 14914 21028 15327 17166 5 -> 2873 7279 6132 13459 11397 0 10318 16608 9740 24042 12298 16140 9845 12432 6541 4023 16886 9238 10016 7794 11408 15927 10809 5108 20001 6 -> 21516 19527 18380 22643 2029 20157 0 7240 21988 14674 11769 6772 18537 21124 23592 16271 19902 8358 19200 16486 23656 16943 23057 17356 9683 7 -> 4918 6218 5071 5220 8774 2045 9257 0 7084 17466 4059 9564 7222 7710 8586 2962 12192 8177 1777 9839 8752 13271 9748 4047 18940 8 -> 11080 3394 2602 4182 6267 9653 6788 9859 0 18912 11180 11010 4715 6672 8305 9564 7146 5708 10058 16001 1668 6187 7136 10649 16471 9 -> 8356 10195 9048 16838 15263 5483 13234 4246 12656 0 17781 20006 15328 9431 8918 6939 19802 12154 15499 13277 13520 2269 13725 8024 22917 10 -> 9747 25083 24307 20333 18271 22139 25754 23482 27915 30916 0 23014 16719 19306 13415 22198 8133 17023 16890 14668 23395 33185 28825 23283 35437 11 -> 16258 12755 11608 19398 4769 13385 2740 9980 15216 7902 14509 0 19931 17333 16820 9499 22362 11098 19064 19226 16884 10171 16285 10584 12423 12 -> 16088 8402 7588 15378 1552 14661 9035 6763 11196 14197 11292 6295 0 2587 13278 5479 18342 10694 15044 21009 6676 16466 12144 6564 18718 13 -> 13501 5815 5001 12791 8688 12074 9187 13899 8609 21333 13883 13431 7136 0 10691 2892 15755 8107 12457 18422 4089 14796 9557 3977 18870 14 -> 11380 11135 12072 6385 14626 8507 13679 7270 15680 3024 9911 19369 13074 8875 0 9963 18044 14899 7629 12544 12964 5293 14877 11048 5741 15 -> 10730 3256 2109 9899 8324 9515 6295 13535 5717 20969 10991 13067 10432 12389 7799 0 12863 5215 9565 15651 7385 11904 6786 1085 15978 16 -> 14448 16287 15140 22930 21355 11575 19326 - 18748 6092 23873 26098 21420 15523 - 13031 0 18246 21591 19369 19612 8361 19817 14116 29009 17 -> 15523 11669 10522 18312 16737 17928 14708 21948 14130 29382 5776 21480 18845 20802 16212 8413 13909 0 17978 20444 15798 20317 15199 9498 24391 18 -> 8122 8193 10934 3443 6997 5249 10737 12208 14542 19642 2282 11740 5445 5933 11790 8825 10415 14040 0 13043 10022 20729 11935 9910 20420 19 -> 17878 10453 9639 17429 3603 16712 11086 8814 13247 16248 8131 8346 2051 4638 15329 7530 16264 2355 17095 0 8727 18517 14195 8615 20769 20 -> 9412 1726 6982 15534 4599 7985 11168 9810 14243 17244 14339 9342 3047 5634 6637 8526 21389 10088 14438 14333 0 19513 5468 9611 20851 21 -> 20663 12977 12163 19953 15850 19236 16349 21061 15771 28495 21045 20593 14298 7162 17853 10054 22917 15269 19619 25584 11251 0 16719 11139 26032 22 -> 3944 19121 17974 14530 11135 16336 9106 16346 21582 14268 13369 6366 10916 13503 7612 15865 21502 11220 11087 8865 17592 16537 0 16950 18789 23 -> 13185 5499 4352 4551 10567 11758 8538 - 15650 9738 11549 15310 14177 7041 6714 9933 - 7458 11808 18106 11130 12007 9241 0 12455 24 -> 17639 17256 16442 12960 10406 14766 17889 15617 20050 23051 11799 15149 8854 11441 21307 14333 19932 9158 9517 6803 15530 25320 20998 15418 0 +++ Cheapest prices with any number of non-AI legs 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 0 -> 0 15336 14560 10586 8524 12392 16007 10938 18168 21169 9425 13267 6972 9559 3668 12451 17558 7276 7143 4921 13648 23438 19078 13536 25690 1 -> 7686 0 5256 13808 11471 6259 9442 9293 15999 18010 14138 10108 14658 16298 11354 10282 17321 8362 12712 12607 17667 20279 3742 11367 19125 2 -> 8833 1147 0 8552 6215 7406 4186 10440 17146 18860 8882 10958 12901 11042 12501 11429 17015 3106 7456 13754 15131 21129 4889 12514 13869 3 -> 12436 4750 7491 0 9323 11009 7294 11709 11099 21968 6998 14066 9626 2490 13181 5382 15131 10597 14947 17357 6579 17286 8492 6467 16977 4 -> 19487 17498 16351 24141 0 18128 7483 5211 19959 12645 9740 4743 24674 22076 9187 14242 13239 15841 23807 23969 21627 14914 21028 15327 17166 5 -> 2873 7279 6132 13459 11397 0 10318 9190 9740 24042 12298 16140 9845 12432 6541 4023 16886 9238 10016 7794 11408 15927 10809 5108 20001 6 -> 21516 19527 18380 22643 2029 20157 0 7240 21988 14674 11769 6772 18537 21124 11216 16271 15268 8358 19200 16486 23656 16943 23057 17356 9683 7 -> 4918 6218 5071 5220 8774 2045 9257 0 7084 17466 4059 9564 7222 7710 8586 2962 12192 8177 1777 9839 8752 13271 9748 4047 18940 8 -> 11080 3394 2602 4182 6267 9653 6788 9859 0 18912 11180 11010 4715 6672 8305 9564 7146 5708 10058 16001 1668 6187 7136 10649 16471 9 -> 8356 10195 9048 16838 15263 5483 13234 4246 12656 0 17781 20006 15328 9431 7681 6939 16438 12154 15499 13277 13520 2269 13725 8024 22917 10 -> 9747 25083 24307 20333 18271 22139 25754 18446 27915 30916 0 23014 16719 19306 12583 22198 8133 17023 16890 14668 23395 33185 28825 23283 35437 11 -> 16258 12755 11608 19398 4769 13385 2740 9980 15216 7902 14509 0 19931 17333 12087 9499 16497 11098 19064 19226 16884 10171 16285 10584 12423 12 -> 16088 8402 7588 15378 1552 14661 9035 6763 11196 14197 11292 6295 0 2587 10739 5479 14791 10694 15044 21009 6676 16466 12144 6564 18718 13 -> 13501 5815 5001 12791 8688 12074 9187 9219 8609 21333 13883 13431 7136 0 10691 2892 13528 8107 12457 18422 4089 14796 9557 3977 18870 14 -> 11380 11135 12072 6385 14626 8507 13679 7270 15680 3024 9911 19369 13074 8875 0 9963 18044 14899 7629 12544 12964 5293 14877 11048 5741 15 -> 10730 3256 2109 9899 8324 9515 6295 12549 5717 20969 10991 13067 10432 12389 7799 0 12863 5215 9565 15651 7385 11904 6786 1085 15978 16 -> 10105 16287 15140 15558 12660 11575 10631 10338 17422 6092 14397 7891 15925 15523 13773 13031 0 9327 12115 13874 15601 8361 11214 14116 13812 17 -> 15523 11669 10522 18312 16737 17928 14708 9736 14130 29382 5776 21480 18845 20802 9499 8413 13909 0 17978 20444 15798 20317 15199 9498 24391 18 -> 8122 8193 10934 3443 6997 5249 10737 8255 14542 19642 2282 11740 5445 5933 11790 8825 10415 14040 0 13043 10022 20729 11935 9910 20420 19 -> 17878 10453 9639 17429 3603 16712 11086 8814 13247 16248 8131 8346 2051 4638 11854 7530 16264 2355 17095 0 8727 18517 14195 8615 20769 20 -> 9412 1726 6982 15534 4599 7985 11168 9810 14243 17244 14339 9342 3047 5634 6637 8526 9439 10088 14438 14333 0 19513 5468 9611 20851 21 -> 20663 12977 12163 19953 15850 19236 16349 12682 15771 28495 21045 20593 14298 7162 5412 10054 19302 15269 19619 25584 11251 0 16719 11139 26032 22 -> 3944 19121 17974 14530 11135 16336 9106 14882 21582 14268 13369 6366 10916 13503 7612 15865 21502 11220 11087 8865 17592 16537 0 16950 18789 23 -> 13185 5499 4352 4551 9581 11758 7552 13984 15650 9738 11549 8392 14177 7041 6714 9933 19682 7458 11808 13640 11130 12007 9241 0 12455 24 -> 17639 17256 16442 12960 10406 14766 17889 15617 20050 23051 11799 15149 8854 11441 18657 14333 16052 9158 9517 6803 15530 25320 20998 15418 0 ----------------------------------------------------------------------------------------------------