A2884. 设计道路
编程题
普及/提高-
知识点
题目描述
Caesar远征高卢回来后，对你大加赞赏，他亲自来到Genoa视察。
Genoa在你的建设下变得无比繁荣，由于财政收入的增加，你为城市修建了交通系统。古罗马的交通系统由两部分组成——Dirt Road和Rome Road。两个路口间只可能是其中一种道路。在Rome Road上可以驾驶马车，而在Dirt Road上则不行。由于修建道路是一项浩大的工程，使得你无法将整个城市用Rome Road连接起来。
现在Caesar已经到达码头，他要求去你家参观。Caesar由一个癖好，喜欢坐车而不喜欢走路。所以Caesar走Dirt Road时的不满值要比走Rome Road时大。
为了不让Caesar过于不满而罢免你的职位，请设计路线使得Caesar的不满值最小。
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