• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ1724 – ROADS

    ACM-POJ EXP 220阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    给定一个图,图中每条路都有 路长Length 和 过路费Toll 两个参数,一条路连接两个城市,任意两个城市之间有且仅有一条路。

    现在只有 K 块钱,要求从起点City1出发,到达终点CityN的最短路,也就是说在 K 花费内的最短路。

    解题思路

    这个题其实有很多种解法的,只不过是题目描述用的模型是最短路的模型,其实方法多种多样,Discuss里有同学用dijkstra+A*算法,也有人用BFS+优先队列,也有人用直接用STL的priotrity_queue+剪枝…..。


    我用了DFS+剪枝去做:

    每个城市只能到达1次,每次找满足 TollMinLen就回溯,无需往下搜索了;递归出口是遍历所有允许的情况。

    其实这题难度不大,关键是建立 邻接链表 去存储相同Source的路径去提高搜索效率。

    因为Bob每进入一个Cityk,他就只能选择以k为源点的路径走向下一个城市,此时应该直接枚举所有以k为源点的路径。若使用了其他存储方式,则必然每次都要在所有路径中重新寻找以k为源点的路径,再枚举,这相当浪费时间。

    Source修正

    CEOI 1998

    测试数据

    本文第三页附带测试数据

    测试数据下载


    风格一: C++

    转载请注明:EXP 技术分享博客 » POJ1724 – ROADS

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址