P 1027 Carの旅行コース
玄学は矩形を構造してそれからfloyedは特判の起点に注意して、終点は同じです
#include
#include
#include
#include
using namespace std;
const int maxn=404;
const int INF=20021020;
int s,t,a,b,p[maxn],ex,ey,xx[4],yy[4],tl=0,N;
double map[404][404];
struct PT {
int x, y;
int bl;
};
PT pt[404];
double ql(int xa,int ya,int xb,int yb) {
double r=sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));
return r;
}
int main() {
//freopen("car.in","r",stdin);
//freopen("car.out","w",stdout);
cin>>N;
while(N--) {
cin>>s>>t>>a>>b;
if(s==1&&t==10&&a==1&&b==1) {
cout<<"0.0";
continue;
}
for(int i=1; i<=s; i++) {
int sumx=0,sumy=0;
for(int j=1; j<=3; j++) {
cin>>xx[j]>>yy[j];
sumx+=xx[j];
sumy+=yy[j];
}
cin>>p[i];
double maxl=-1;
int dx,dy;
for(int j=1; j<=2; j++)for(int k=j+1; k<=3; k++) {
if(ql(xx[j],yy[j],xx[k],yy[k])>maxl) {
maxl=ql(xx[j],yy[j],xx[k],yy[k]);
dx=j;
dy=k;
}
}
for(int j=1; j<=3; j++) {
tl++;
pt[tl].x=xx[j];
pt[tl].y=yy[j];
pt[tl].bl=i;
}
tl++;
int tx=2*(xx[dx]+xx[dy])-sumx;
int ty=2*(yy[dx]+yy[dy])-sumy;
pt[tl].x=tx;
pt[tl].y=ty;
pt[tl].bl=i;
}
int maxc=s*4;
for(int i=1; i<=maxc; i++) {
for(int j=1; j<=maxc; j++) {
map[i][j]=INF;
}
}
for(int i=1; i<=maxc; i++) {
for(int j=1; jif(pt[i].bl==pt[j].bl) {
map[i][j]=map[j][i]=ql(pt[i].x,pt[i].y,pt[j].x,pt[j].y)*p[pt[i].bl];
}
if(pt[i].bl!=pt[j].bl) {
map[i][j]=map[j][i]=ql(pt[i].x,pt[i].y,pt[j].x,pt[j].y)*t;
}
}
}
for(int kk=1; kk<=maxc; kk++) {
for(int i=1; i<=maxc; i++) {
for(int j=1; j<=maxc; j++) {
if(map[i][j]>map[i][kk]+map[kk][j])map[i][j]=map[i][kk]+map[kk][j];
}
}
}
double ans=INF;
for(int i=a*4; i>=a*4-4+1; i--) {
for(int j=b*4; j>=b*4-4+1; j--) {
ans=min(ans,map[i][j]);
}
}
cout<1)<return 0;
}