记录编号	395454	评测结果	AAAAA
题目名称	[NOIP 2001]Car的旅行路线	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2017-04-16 06:38:15	内存使用	1.60 MiB

#include <cstdio>
#include <queue>
#include <cmath>
#define Rep(i,_z,_zz) for (int i = _z; i <= _zz; i++)
struct pii{double x,y;void in() {scanf("%lf%lf",&x,&y);}}a[4000];
double dis(pii a,pii b) {return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));}
pii calc(pii a,pii b,pii c) {return (pii){a.x+b.x-c.x,a.y+b.y-c.y};}
void init(int k) {
        a[k].in();a[k+1].in();a[k+2].in();
        double ab = dis(a[k],a[k+1]),ac = dis(a[k],a[k+2]),bc = dis(a[k+1],a[k+2]),m = std::max(ab,std::max(ac,bc));
        if(ab == m) a[k+3] = calc(a[k],a[k+1],a[k+2]);
        if(ac == m) a[k+3] = calc(a[k],a[k+2],a[k+1]);
        if(bc == m) a[k+3] = calc(a[k+1],a[k+2],a[k]);
};
int tt[404],s,t,A,B; double f[404][404];
double cost(int x,int y) {return (x-1)/4 == (y-1)/4?dis(a[x],a[y])*tt[(x-1)/4+1]:dis(a[x],a[y])*t;}
void work() {
    scanf("%d%d%d%d",&s,&t,&A,&B);
    for (int i = 1; i <= s; i++) init((i-1)*4+1),scanf("%d",&tt[i]);
    int n = s<<2;double ans = 2147483647;
    Rep (i,1,n) Rep (j,1,n) f[i][j] = cost(i,j);
    Rep (k,1,n) Rep (i,1,n) if(k!=i) Rep (j,1,n)
       if(j!=k && j!=i) f[i][j] = std::min(f[i][j],f[i][k]+f[k][j]);
    Rep(i,(A-1)*4+1,(A-1)*4+4) Rep(j,(B-1)*4+1,(B-1)*4+4) ans = std::min(ans,f[i][j]);
    printf("%.1f\n",ans);
}
int main() {
   freopen("cardlxlx.in","r",stdin); freopen("cardlxlx.out","w",stdout);
   int n; for(scanf("%d",&n); n-- ;work());
   return 0;
}