Aimee

非常简单

运用一点点的数学知识算出两两之间的距离

然后跑最短路

#include
#include
#include
#include
#include
using namespace std;
int xx,yy,xxx,yyy,xxxx,yyyy,xxxxx,yyyyy;
int su[10001];
int n;
double dis[1001][1001];
struct ci{
    int x;
    int y;
    int id;
}city[40001];
int s,t,a,b;
int  f(int x){
    return x*x;
}
int p;
void crea(int x,int y,int id){
    p++;
    city[p].x=x;
    city[p].y=y;
    city[p].id=id;
}
double cd(int x,int y){
    return sqrt(f(city[x].x-city[y].x)+f(city[x].y-city[y].y));
}
double mx,my;
void build(int id){
    crea(xx,yy,id); crea(xxx,yyy,id);   crea(xxxx,yyyy,id);
    int ab=f(xx-xxx)+f(yy-yyy);
    int ac=f(xx-xxxx)+f(yy-yyyy);
    int bc=f(xxx-xxxx)+f(yyy-yyyy);
    if(ab==ac+bc) {
        mx=(xx+xxx)/2;
        my=(yy+yyy)/2;
        xxxxx=2*mx-xxxx;
        yyyyy=2*my-yyyy;
    }
    if(ac==ab+bc) {
        mx=(xx+xxxx)/2;
        my=(yy+yyyy)/2;
        xxxxx=2*mx-xxx;
        yyyyy=2*my-yyy;
    }
    if(bc==ab+ac) {
        mx=(xxx+xxxx)/2;
        my=(yyy+yyyy)/2;
        xxxxx=2*mx-xx;
        yyyyy=2*my-yy;
    }
    crea(xxxxx,yyyyy,id);
}
double co(int x,int y){
    if(city[x].id==city[y].id){
        return cd(x,y)*su[city[x].id];
    }else{
        return cd(x,y)*t;
    }
}
double Aimee;
int main(){
    scanf("%d",&n);
    while(n--){
        Aimee=99999999.999;
        scanf("%d%d%d%d",&s,&t,&a,&b);
        for(int i=1;i<=s;++i){
            scanf("%d%d%d%d%d%d%d",&xx,&yy,&xxx,&yyy,&xxxx,&yyyy,&su[i]);
            build(i);
        }
    for(int i=1;i<=p;++i){
        for(int j=i;j<=p;++j){
            if(i==j)
            dis[i][j]=dis[j][i]=0;
            else
            dis[i][j]=dis[j][i]=co(i,j);
        }
    }
    for(int k=1;k<=p;++k){
        for(int i=1;i<=p;++i){
            for(int j=1;j<=p;++j){
                if(dis[i][k]+dis[k][j]