又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一 条笔直的高速铁路，第I个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。
　　那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题，于是她来向你请教。
　　找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。

　　数据的第一行有四个正整数s，t，A，B。
　　S表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B的序号，(1<=A，B<=S)。
　　接下来有S行，其中第I行均有7个正整数x_i1，y_i1，x_i2，y_i2，x_i3，y_i3，T_i，这当中的(x_i1，y_i1)，(x_i2，y_i2)，(x_i3，y_i3)分别是第I个城市中任意三个机场的坐标，T_l为第I个城市高速铁路单位里程的价格。

输出格式

　　共有n行，每行一个数据对应测试数据，保留一位小数。

 

 

 

 

 

 

 对于100%的数据，  1 <= n <= 10, 1 <= S <= 100, 1 <= A, B <= S.

 

 

 

#include <bits/stdc++.h>

using namespace std;

#define N 401

#define isdigit(c) ((c)>='0'&&(c)<='9')

#define min(a,b) ((a)>(b)?(b):(a))

/*比 STL 快？*/ 

inline int read(){

    int x = , s = ;

    char c = getchar();

    while(!isdigit(c)){

        if(c == '-') s = -;

        c = getchar();

    }

    while(isdigit(c)){

        x = (x << ) + (x << ) + (c ^ '');

        c = getchar();

    }

    return x * s;

}

struct node{//存每个机场的信息

    int x, y;

    int city, price;

} t[N << ];

double d[N << ];

int n, pla_pri, s, ht;

inline int square(int x){

    return x * x;

}

inline int dis(int a, int b){//暂时先不开根号，使用起来方便一些

    return square(t[a].x - t[b].x) + square(t[a].y - t[b].y); //编号机场的距离

}

inline void get4(int n1,int n2,int n3){

    int x4, y4;

    int x1 = t[n1].x, y1 = t[n1].y, x2 = t[n2].x, y2 = t[n2].y, x3 = t[n3].x, y3 = t[n3].y;

    int ab = dis(n1, n2);

    int ac = dis(n1, n3);

    int bc = dis(n2, n3);

    if(ab == ac + bc) x4 = x1 + x2 - x3, y4 = y1 + y2 - y3;//勾股定理，求出第四个点

    else if(ac == ab + bc) x4 = x1 + x3 - x2, y4 = y1 + y3 - y2;

    else if(bc == ac + ab) x4 = x2 + x3 - x1, y4 = y2 + y3 - y1;

    t[n3+].x = x4, t[n3+].y = y4;

/*    printf("x1:%d y1: %d x2: %d y2: %d x3: %d y3: %d x4: %d y4: %d\n", x1,y1,x2,y2,x3,y3,x4,y4);

    分段检查程序可以防止写完之后 Debug 两小时 */

    return ;

}

void init(){

    int cac_city = ;

    for(int i = ;i <= (n << ); i += ){

        t[i].x = read(), t[i].y = read();

        t[i+].x = read(), t[i+].y = read();

        t[i+].x = read(), t[i+].y = read();

        t[i].price = t[i+].price = t[i+].price = t[i+].price = read();//把价格记录下来

        t[i].city = t[i+].city = t[i+].city = t[i+].city = ++cac_city;//城市记录下来

        get4(i, i+, i+);//寻找第四个点

    }

    return ;

}

queue <int> q;

bool vis[N << ];

void spfa(){

    /*时刻不忘 n 是4倍！！不然玄学错误！！*/

    for(int i = ;i <= (n << ); i++)

        d[i] = 99999999.99;

    for(int i =  * (s - ) + ;i <=  * (s - ) + ; i++){//都能作为起点，所以4个点全部推进去

        vis[i] = ;

        q.push(i);

        d[i] = ;

    }

    while(!q.empty()){//SPFA

        int now = q.front();q.pop();

        vis[now] = ;

        for(int i = ;i <= (n << ); i++){//反正全部有连边，直接 for 循环不香吗

            if(i == now)continue;

            double cost;

            if(t[i].city == t[now].city){//如果在同一个城市

                cost = t[i].price * (double)sqrt((double)dis(i, now));

            }

            else cost = pla_pri * (double)sqrt((double)dis(i, now));//连边的价值（距离）

            if(d[i] > d[now] + cost){

                d[i] = d[now] + cost;

                if(!vis[i]){

                    vis[i] = ;

                    q.push(i);

                }

            }

        }

    }

    return ;

}

int main(){

//    freopen("hh.txt", "r", stdin);

    int T = read();

    while(T--){

        n = read(), pla_pri = read(), s = read(), ht = read();

        if(s == ht){  //这里用SPFA可以不特判，但是如果用Floyd就要特判了 （初始化成了极大值）

            puts("0.0");

            continue;

        }

        init();

        spfa();

        double ans = ~0u >> ;

        for(int i =  * (ht - ) + ;i <=  * (ht - ) +  + ; i++)

            ans = min(d[i], ans);//答案为终点四个机场里面最小的

        printf("%.1lf\n", ans);

    }

    return ;

}