P1907 设计道路

    • 136通过
    • 278提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 图论
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Caesar远征高卢回来后,对你大加赞赏,他亲自来到Genoa视察。

    Genoa在你的建设下变得无比繁荣,由于财政收入的增加,你为城市修建了交通系统。古罗马的交通系统由两部分组成——Dirt Road和Rome Road。两个路口间只可能是其中一种道路。在Rome Road上可以驾驶马车,而在Dirt Road上则不行。由于修建道路是一项浩大的工程,使得你无法将整个城市用Rome Road连接起来。

    现在Caesar已经到达码头,他要求去你家参观。Caesar由一个癖好,喜欢坐车而不喜欢走路。所以Caesar走Dirt Road时的不满值要比走Rome Road时大。

    为了不让Caesar过于不满而罢免你的职位,请设计路线使得Caesar的不满值最小。

    输入输出格式

    输入格式:

    输入数据第一行有两个实数,分别表示走Dirt Road和Rome Road一个单位长度时Caesar的不满值。接下来是一个整数N(N<=1000),代表路口总数。接下来有N行,每行一组实数(x,y)分别描述这N个路口的坐标。接下来有若干行,每行一组整数(i,j),表示第i个路口与第j个路口间为Rome Road,以0 0结束。最后两行,每行一对实数,分别描述码头和你家的坐标。

    输出格式:

    输出Caesar从码头到你家的最小不满值,保留4位小数

    输入输出样例

    输入样例#1: 复制
    100.0 2.0
    2
    1.0 0.0
    2.0 1.0
    1 2
    0 0
    0.0 0.0
    2.0 2.0
    
    输出样例#1: 复制
    202.8284
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。