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

#include<bits/stdc++.h>
using namespace std;
int q,s,t,A,B;
double jl(int x1,int y1,int x2,int y2){
    return sqrt(((x1-x2)*(x1-x2))+((y1-y2)*(y1-y2)));
}
int main(){
    freopen("cardlxlx.in","r",stdin);
    freopen("cardlxlx.out","w",stdout);
    cin>>q;
    while(q--){
        cin>>s>>t>>A>>B;
        double a[110][8],gt[110];
        int top=0;
        double nm[110][110];
        double minx=INT_MAX;
        for(int i=1;i<=s*4;i++){
            for(int j=1;j<=s*4;j++)
            nm[i][j]=INT_MAX;
        }
        for(int i=1;i<=s;i++){
            cin>>a[i][1]>>a[i][2]>>a[i][3]>>a[i][4]>>a[i][5]>>a[i][6]>>gt[i];
            double l12,l13,l23,l14,l24,l34;
            l12=jl(a[i][1],a[i][2],a[i][3],a[i][4])*1.0,l13=jl(a[i][1],a[i][2],a[i][5],a[i][6])*1.0,l23=jl(a[i][5],a[i][6],a[i][3],a[i][4])*1.0;
            int maxx=max(l12,max(l13,l23));
            if(l13>l12&&l13>l23){
                a[i][7]=a[i][1]+a[i][5]-a[i][3];
                a[i][8]=a[i][2]+a[i][6]-a[i][4];
            }
            if(l12>l13&&l12>l23){
                a[i][7]=a[i][1]+a[i][3]-a[i][5];
                a[i][8]=a[i][2]+a[i][4]-a[i][6];
            }
            if(l23>l12&&l23>l13){
                a[i][7]=a[i][3]+a[i][5]-a[i][1];
                a[i][8]=a[i][6]+a[i][4]-a[i][2]; 
            }
            l14=jl(a[i][1],a[i][2],a[i][7],a[i][8])*1.0,l34=jl(a[i][7],a[i][8],a[i][5],a[i][6])*1.0,l24=jl(a[i][7],a[i][8],a[i][3],a[i][4])*1.0;
            nm[top+1][top+2]=l12*gt[i]*1.0,nm[top+1][top+3]=l13*gt[i],nm[top+2][top+3]=l23*gt[i]*1.0,nm[top+1][top+4]=l14*gt[i],nm[top+2][top+4]=l24*gt[i]*1.0,nm[top+3][top+4]=l34*gt[i]*1.0;
            nm[top+2][top+1]=l12*gt[i]*1.0,nm[top+3][top+1]=l13*gt[i],nm[top+3][top+2]=l23*gt[i]*1.0,nm[top+4][top+1]=l14*gt[i],nm[top+4][top+2]=l24*gt[i]*1.0,nm[top+4][top+3]=l34*gt[i]*1.0;
            top+=4; 
        }   
        for(int i=1;i<=s;i++){
            for(int j=1;j<=s;j++){
                for(int k=1;k<=4;k++){
                    for(int u=1;u<=4;u++){
                        if(i!=j){
                            nm[(i-1)*4+k][(j-1)*4+u]=jl(a[i][(k-1)*2+1],a[i][(k-1)*2+2],a[j][(u-1)*2+1],a[j][(u-1)*2+2])*t*1.0;
                        }
                }
            }
        }
    }
        for(int i=1;i<=top;i++)
        nm[i][i]=0;
        for(int k=1;k<=top;k++){
            for(int i=1;i<=top;i++){
                for(int j=1;j<=top;j++){
                    nm[i][j]=min(nm[i][j],nm[i][k]+nm[k][j]);
                }
            }
        }
        for(int i=1;i<=s;i++){
            for(int j=i;j<=top;j++){
            }
        }
        for(int i=1;i<=4;i++){
            for(int j=1;j<=4;j++){
                if(minx>nm[(A-1)*4+i][(B-1)*4+j])
                minx=nm[(A-1)*4+i][(B-1)*4+j];
            }
        }
        printf("%.1lf\n",minx);
    }
    return 0;
}