这题可以说很水，但是得细心，我前几次的WA都在以为考虑了的地方，结果debug之后才知道忽略了。
1.所有的点到其他所有的点，都可以步行过去。
2.只有相邻的地铁站可以乘车。
这里面有个代码技巧的问题，我先做了第二补，然后在做第一步。（目的是可以在赋值的时候直接做到，其实并没有节约循环和时间）所以我的两个函数名字为。
switch_line_walk_cost 和 adjacent_stop_cost 意思是换乘开销和乘车开销。
但是这里面有一个问题没有考虑到，实际生活中如果以要乘车从第一站到第三站，你应该一直待在车上（地铁要比步行快4倍）但是这题的数据却需要蛋疼得让你从第一站直接走到第三站去。
比如说 地铁线 line1 A -- B -- C 如果 A和C的坐标很近，但是B的坐标非常远。乘车从A经B到C的开销甚至超过了直接从A走到C的开销时，这样也可以认为需要换乘（步行）。我对于这一点没有考虑到，导致我WA了很久楞是没查出错在哪了？
最后，调整了一下代码。先将每一个节点的步行时间计算出来，然后用乘车时间去更新换乘点的时间。于是AC了，值得一题的是这题做的人比较少，又一次排到C语言的第二名。悲催的是，又一次小号比大号的排名靠前！！
由于代码很上一贴差不多，就不给出来了。多亏了以下数据，让我查出自己的错误。
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 阅读(325)
评论(0) 编辑 收藏 引用