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

    ACM-POJ EXP 170阅读 0评论

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


    提示

    唉。。不说了,又是Floyd…注意精度就是了

    题目大意

    给出两只青蛙的坐标A、B,和其他的n-2个坐标,任一两个坐标点间都是双向连通的。显然从A到B存在至少一条的通路,每一条通路的元素都是这条通路中前后两个点的距离,这些距离中又有一个最大距离。

    现在要求求出所有通路的最大距离,并把这些最大距离作比较,把最小的一个最大距离作为青蛙的最小跳远距离。

    解题思路

    用Floyd算法求出两两最短路,再求出从每个点开始的最长路,最后从这n个最长路中求出最小的那个即为所求。

    转载请注明:EXP 技术分享博客 » POJ2253 – Frogger

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

    表情

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

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