主要用到了并查集判点是否在同一个城市

其次就是Floyd了

#include<bits/stdc++.h>
#define For(i,m,n) for(register ll i=m;i<n;i++)
#define rFor(i,m,n) for(register ll i=m;i>n;i--)
#define r(a) read(a)
#define rr(a,b) read(a),read(b)
#define rrr(a,b,c) read(a),read(b),read(c)
using namespace std;
typedef long long ll;
typedef unsigned long long Ull;
template <class T>
inline void read(T &x)
{
	x=0;
    T f=1;
    char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	x=x*f;
}
const ll MaxN = 1e2+20, MaxM = 2*1e6+500;
const ll SMALL_INF=2147483647000000;
const ll MOD=100003;
const double DOUBLE_INF=1e20;
struct state{
    double x;
    double y;
    double T;
};

struct edge{
    int u;
    int v;
    double w;
}e[MaxM<<1];

int n,s,t,a,b;
state point[MaxN];
int cntPoint=1;
int f[MaxN];
int Rank[MaxN];
int cntFa=1;
int find_root(int x)
{
    if(f[x]==x)     return x;
    return f[x]=find_root(f[x]);
}
void Union(int x,int y)
{
    int x_root=find_root(x);
    int y_root=find_root(y);
    if(x_root==y_root)  return;
    if(Rank[x_root]>Rank[y_root]){
        f[y_root]=x_root;
    }
    else if(Rank[x_root]<Rank[y_root]){
        f[x_root]=y_root;
    }
    else{
        f[x_root]=y_root;
        Rank[y_root]++;
    }
}
void init()
{
    For(i,1,MaxN+1){
        f[i]=i;
        Rank[i]=0;
    }

        int cntPoint=1;
        int cntFa=1;


}
double getDis(state n1,state n2)
{
    return sqrt(pow(n1.x-n2.x,2)+pow(n1.y-n2.y,2));
}

state getNextPos(vector<state> A)
{
    double dis1=getDis(A[0],A[2]);
    double dis2=getDis(A[2],A[1]);
    state nxt=A[2];
    if(dis1<dis2){
        nxt.x=A[2].x-(A[0].x-A[1].x);
        nxt.y=A[2].y-(A[0].y-A[1].y);
    }
    else{
        nxt.x=A[2].x+(A[0].x-A[1].x);
        nxt.y=A[2].y+(A[0].y-A[1].y);
    }
    return nxt;
}
double dist[MaxN][MaxN];
void input()
{
    r(n);
    For(i,0,n){
        rr(s,t),rr(a,b);
        init();
        For(i,1,MaxN+1)    For(j,1,MaxN+1)    if(i!=j)    dist[i][j]=1e21;
        For(i,1,s+1){
            vector<state> A;
            double T;
            For(j,0,3){
                state now;
                cin>>now.x>>now.y;
                A.push_back(now);
            }
            A.push_back(getNextPos(A));
            cin>>T;
            For(k,0,A.size())   A[k].T=T;

            For(k,0,A.size())   point[cntPoint++]=A[k];
            For(k,1,5){
                For(p,1,5){
                    if(k!=p)    Union(cntPoint-k,cntPoint-p);
                }
            }

        }
        For(i,1,cntPoint){
            For(j,1,cntPoint){
                if(i==j){
                    continue;
                }
                int xr,yr;
                xr=find_root(i);
                yr=find_root(j);
                if(xr!=yr)  dist[i][j]=getDis(point[i],point[j])*t;
                else        dist[i][j]=getDis(point[i],point[j])*point[i].T;
            }
        }
    }

}



void Floyd()
{
    For(k,1,cntPoint){
        For(i,1,cntPoint){
            For(j,1,cntPoint){
                //可以用于负环
                double t=dist[i][k]+dist[k][j];
                if(dist[i][j]>t){
                    dist[i][j]=t;
                    dist[j][i]=t;
                }
            }
        }
    }
}

void show()
{

}

int main()
{
    input();
    Floyd();
    double res=1e21;
    For(i,(a-1)*4+1,(a-1)*4+5){
        For(j,(b-1)*4+1,(b-1)*4+5){
            res=min(res,dist[i][j]);
        }
    }
    printf("%.1lf",res);
    return 0;
}