A22597.设计道路

普及/提高-

通过率:0%

时间限制:1.00s

内存限制: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

说明/提示

首页