← 返回题目
题库练习 设计道路
← 上一题 下一题 →

A2884 | 设计道路

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

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
C++ 编辑器
输入
输出