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

    ACM-POJ EXP 204阅读 0评论

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


    解题思路

    利用虫洞的时光旅行,很有趣的一道题。涉及到图论的知识,关键是构造图,用Bellman-Ford算法找出负权环

    Bellman-Ford算法核心在于松弛,具体可以百度,这里就不重复前人的智慧了O(∩_∩)O哈哈~

    需要注意的就是输入说明Input这部分,很多人读不懂这段题意

    正权(双向)边部分

    Line 1 of each farm: Three space-separated integers respectively: N, M, and W

    Lines 2~M+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse.

    Two fields might be connected by more than one path.

    负权(单向)边部分

    Lines M+2~M+W+1 of each farm: Three space-separated numbers (S,E, T) that describe, respectively: A one way path from S toE that also moves the traveler back T seconds.

    转载请注明:EXP 技术分享博客 » POJ3259 – Wormholes

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

    表情

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

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