记录编号	581188	评测结果	AAAAA
题目名称	[NOIP 2001]Car的旅行路线	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-07-31 10:38:54	内存使用	0.00 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 410,M = 200010;
int t,n,su,s,tu;
struct made{
    int ver,nx;
    double ed;//边权要为浮点数 
}e[M];//链式前项星，邻接表存 
int hd[N],tot; 
bool v[N];//spfa 
double d[N],T[N],ans = 100000000;//T为输入的城市高速铁路单位里程的价格
//d为最短路数组 ans为所求答案即最小值 
struct node{
    double x,y;
}zu[N][10];
void add_(int x,int y,double z){
    tot++;
    e[tot].ver = y,e[tot].ed = z,e[tot].nx = hd[x],hd[x] = tot;
}//建边 
double dis(node x,node y){
    return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y));
}//两点之间坐标距离公式 
void four_(int x){
    double s1 = dis(zu[x][1],zu[x][2]),s2 = dis(zu[x][2],zu[x][3]),s3 = dis(zu[x][3],zu[x][1]);
    //长度最长的是直角中的斜边 
    if(s1 > s2 && s1 > s3){
        zu[x][4].x = zu[x][1].x + zu[x][2].x - zu[x][3].x;
        zu[x][4].y = zu[x][1].y + zu[x][2].y - zu[x][3].y;
    }
    else if(s2 > s1 && s2 > s3){
        zu[x][4].x = zu[x][3].x + zu[x][2].x - zu[x][1].x;
        zu[x][4].y = zu[x][3].y + zu[x][2].y - zu[x][1].y;
    }
    else if(s3 > s1 && s3 > s1){
        zu[x][4].x = zu[x][1].x + zu[x][3].x - zu[x][2].x;
        zu[x][4].y = zu[x][1].y + zu[x][3].y - zu[x][2].y;
    }//利用矩形和中点坐标公式求出第四个飞机场 
}
void init(){
    tot = 0;
    memset(zu,0,sizeof(zu));
    memset(e,0,sizeof(e));
    memset(hd,0,sizeof(hd));
    memset(T,0,sizeof(T));//多组数据要重置 
    scanf("%d%d%d%d",&n,&su,&s,&tu);
    for(int i = 1;i <= n;i++){
        scanf("%lf%lf%lf%lf%lf%lf%lf",&zu[i][1].x,&zu[i][1].y,&zu[i][2].x,&zu[i][2].y,&zu[i][3].x,&zu[i][3].y,&T[i]);
        four_(i);//找第4个 
    }
    for(int i = 1;i <= n;i++){
        for(int ii = 1;ii <= 4;ii++){
            for(int j = 1;j <= n;j++){
                for(int jj = 1;jj <= 4;jj++){
                    //第i个城市的第j个飞机站的节点编号为(i-1)*4+j 
                    if(i == j){//如果为同一个城市则做高速公路 
                        if(ii == jj)continue;//自己到自己没有边 
                        add_((i - 1) * 4 + ii,(j - 1) * 4 + jj,T[i] * dis(zu[i][ii],zu[j][jj]));
                        //cout<<i<<' '<<ii<<' '<<j<<' '<<jj<<' '<<T[i] * dis(zu[i][ii],zu[j][jj])<<endl;
                    }
                    else{//不同城市做飞机
                        //su为飞机单位里程的价格 
                        add_((i - 1) * 4 + ii,(j - 1) * 4 + jj,su * dis(zu[i][ii],zu[j][jj]));
                        //cout<<i<<' '<<ii<<' '<<j<<' '<<jj<<' '<<su * dis(zu[i][ii],zu[j][jj])<<endl;
                    }
                }
            }
        }
    }
}
void spfa(int x){
    memset(v,0,sizeof(v));
    for(int i = 1;i <= 4 * n;i++)d[i] = INT_MAX;//因为有4*n个节点，所以初始化到4*n 
    queue<int>q;
    v[x] = 1,d[x] = 0;
    q.push(x);
    while(!q.empty()){
        int x = q.front();q.pop();
        v[x] = 0;
        for(int i = hd[x];i;i = e[i].nx){
            int y = e[i].ver;double z = e[i].ed;
            if(d[x] + z < d[y]){
                d[y] = d[x] + z;
                if(!v[y])q.push(y),v[y] = 1;
            }
        }
    }
}//正常spfa 
int main(){
    freopen("cardlxlx.in","r",stdin);
    freopen("cardlxlx.out","w",stdout);
    scanf("%d",&t);
    while(t--){
        ans = 100000000;//重置 
        init();
        for(int i = 1;i <= 4;i++){
            spfa((s - 1) * 4 + i);//第s个城市的第i个飞机站开始 
            for(int j = 1;j <= 4;j++){
                ans = min(ans,d[(tu - 1) * 4 + j]);//到第tu个城市的j个飞机站结束 
            }
        }
        printf("%.1lf\n",ans);
    }
    
    return 0;
    
}