這題可以說(shuō)很水，但是得細(xì)心，我前幾次的WA都在以為考慮了的地方，結(jié)果debug之后才知道忽略了。
1.所有的點(diǎn)到其他所有的點(diǎn)，都可以步行過(guò)去。
2.只有相鄰的地鐵站可以乘車(chē)。
這里面有個(gè)代碼技巧的問(wèn)題，我先做了第二補(bǔ)，然后在做第一步。（目的是可以在賦值的時(shí)候直接做到，其實(shí)并沒(méi)有節(jié)約循環(huán)和時(shí)間）所以我的兩個(gè)函數(shù)名字為。
switch_line_walk_cost 和 adjacent_stop_cost 意思是換乘開(kāi)銷(xiāo)和乘車(chē)開(kāi)銷(xiāo)。
但是這里面有一個(gè)問(wèn)題沒(méi)有考慮到，實(shí)際生活中如果以要乘車(chē)從第一站到第三站，你應(yīng)該一直待在車(chē)上（地鐵要比步行快4倍）但是這題的數(shù)據(jù)卻需要蛋疼得讓你從第一站直接走到第三站去。
比如說(shuō) 地鐵線 line1 A -- B -- C 如果 A和C的坐標(biāo)很近，但是B的坐標(biāo)非常遠(yuǎn)。乘車(chē)從A經(jīng)B到C的開(kāi)銷(xiāo)甚至超過(guò)了直接從A走到C的開(kāi)銷(xiāo)時(shí)，這樣也可以認(rèn)為需要換乘（步行）。我對(duì)于這一點(diǎn)沒(méi)有考慮到，導(dǎo)致我WA了很久楞是沒(méi)查出錯(cuò)在哪了？
最后，調(diào)整了一下代碼。先將每一個(gè)節(jié)點(diǎn)的步行時(shí)間計(jì)算出來(lái)，然后用乘車(chē)時(shí)間去更新?lián)Q乘點(diǎn)的時(shí)間。于是AC了，值得一題的是這題做的人比較少，又一次排到C語(yǔ)言的第二名。悲催的是，又一次小號(hào)比大號(hào)的排名靠前??！
由于代碼很上一貼差不多，就不給出來(lái)了。多虧了以下數(shù)據(jù)，讓我查出自己的錯(cuò)誤。
1 1 10001 10001
2777 886 7793 6915 5386 8335 6649 492 2362 1421 8690 27 7763 59 540 3926 9172 3426 5211 5736 2567 5368 5782 6429 2862 1530 4067 5123 3929 3135 4022 9802 3069 3058 1393 8167 5011 8456 6229 8042 4421 7373 3784 4919 5198 8537 8315 4324 6413 4370 6091 3526 9956 8980 6862 1873 6996 9170 2305 7281 7084 925 336 6327 846 6505 1313 1729 6124 5857 9582 3895 8814 545 5434 3367 4043 364 1087 3750 7276 6808 5788 7178 5403 3584 2754 2651 9932 2399 9676 5060 7739 3368 6226 12 8094 8586 795 7539 1434 570 7467 378 97 6601 3317 2902 6652 492 7301 756 4286 280 3865 9441 8444 9689 8440 6619 8031 4729 8097 8117 4481 5771 709 675 4567 8927 9497 7856 4586 2353 5306 6965 6219 4683 1528 8624 5732 2871 9503 8829 8270 19 9708 3368 6340 6715 7796 8149 2618 723 2846 2245 2921 3451 2379 3555 7764 7488 9841 8228 5193 2350 7034 1500 124 7764 6987 4914 3743 5856 2227 6491 9859 8365 1432 1936 6437 2551 3275 9228 1474 5407 8858 6121 6029 4395 8235 1237 5818 3793 6143 4428 5928 1011 8776 9529 4443 2404 4613 5763 8606 4538 2904 6840 5128 4818 7369 688 9917 7917 3324 6996 9470 7743 8490 2183 9772 5499 5644 6725 7505 5590 2954 8139 7669 9786 8542 8082 197 8464 9355 9507 6348 8804 3622 8611 9299 7828 5746 7343 4340 5568 3311 5422 7605 3810 5661 1801 4878 3730 9320 1305 9444 8736 8522 8626 6708 3465 8282 3416 2924 3258 2062 7637 2600 5624 3452 2036 9379 1899 7468 5550 973 71 3881 7131 8933 4930 8660 5894 7199 163 8899 7981 2959 2996 2813 3773 7190 9668 2926 1095 5084 6466 2090 1340 3376 7684 5936 5542 7445 9107 9179 9756 6887 8418 3348 9412 1659 2172 2336 2009 6342 5210 8206 7587 7713 9301 5321 7372 4819 1255 7721 4599 5939 9904 -1 -1
5667 3940 6228 1705 9150 1127 6658 5984 9224 3920 7269 2422 4081 1396 84 5630 1972 9292 3850 7672 5385 7625 9299 1222 6042 6640 713 3898 6190 2298 -1 -1
8209 2590 8819 8581 7732 9336 5994 1155 -1 -1
4769 379 1776 5273 7255 8850 8142 1860 5884 5579 3205 1993 -1 -1
2504 9567 1961 613 1326 2754 8944 4259 3202 8202 6784 3506 2842 2021 -1 -1
5189 9528 9908 8872 -1 -1
------------------------
36
http://zhidao.baidu.com/question/157000415.html?push=keyword
posted on 2011-05-14 16:27
margin 閱讀(356)
評(píng)論(0) 編輯 收藏 引用