P1027 [NOIP2001 提高组] Car 的旅行路线
题目地址：https://www.luogu.com.cn/problem/P1027
大致题意
每个城市有4个机场，分别位于一个矩形的4个顶点，给出矩形的任意三个顶点，找到第四个顶点，构建无向完全图，找A城到B城的最小花费路径。
思路
找到第四个点
首先找到已有的三点构成三角形的最长边，由题目可知一定是直角三角形，由直角三角形和矩形性质可知，最长边对应的两点一定互为矩形对角线上的点。然后设这两个互为对角线的点分别为\(p_0\)和\(p_2\)，剩下的点为\(p_1\)（三个点分别为\(p_0\)，\(p_1\)，\(p_2\)，第四个点为\(p_3\)），将每条边看作向量，设向量\(\vec{a}=p_0-p_1\)，向量\(\vec{b}=p_2-p_1\)。画出每种可能情况分析几何图形，得到\(p_3=p_0+\vec{b}\)或者\(p_3=p_2+\vec{a}\)。
构建邻接表描述完全图
因为题意是稠密图，使用邻接表描述，邻接表存储所有路径的花费。先对每个机场的四个点进行初始化（机场内使用高铁通行），再对所有没有初始化过的所有点进行初始化（机场之间使用飞机通行）。
Floyd算法求最小花费路径
由于题目数据很小，\(O(n^3)\)完全够用，直接使用Floyd求每个点的最小花费路径，然后遍历所有A城到B城的点找最小值即为答案。
测试样例
样例输入
1
3 10 1 3
1 1 1 3 3 1 30
2 5 7 4 5 2 1
8 6 8 8 11 6 3
样例输出
47.5
代码
//找到第四个点然后最短路径算法找最小值
#include<bits/stdc++.h>
using namespace std;
const int MAX=100+5;
const int MMAX=4*100+5;
const double MMMAX=999999999;
double dp[MMAX][MMAX]={{0}},mp[MMAX][MMAX]={{0}};//[出发][到达]
int n,s,t,a,b,T[MAX]={0};
double u[MMAX][2]={{0}};//[点][x,y]
double ans=MMMAX;
vector<double> point;
double dis(int i,int j){
return sqrt(pow(abs(u[i][0]-u[j][0]),2)+pow(abs(u[i][1]-u[j][1]),2));
}
//找第四个点
vector<double> find(int j){
vector<double> ve;
double p0[2]={0},p1[2]={0},p2[2]={0};
int a1,b1,c1;
double a0,b0,c0,a[2]={0},b[2]={0};
a0=dis(0+j,1+j);
b0=dis(0+j,2+j);
c0=dis(1+j,2+j);
if(a0>b0){
if(c0>a0){//1 2
a1=1;b1=2;c1=0;
}
else if(c0<a0){//0 1
a1=0;b1=1;c1=2;
}
else{//错误
cout<<"error"<<endl;
}
}
else if(a0<b0){
if(c0>b0){//1 2
a1=1;b1=2;c1=0;
}
else if(c0<b0){//0 2
a1=0;b1=2;c1=1;
}
else{//错误
cout<<"error"<<endl;
}
}
else{
if(c0>a0){//1 2
a1=1;b1=2;c1=0;
}
else if(c0<a0){//错误
cout<<"error"<<endl;
}
else{//错误
cout<<"error"<<endl;
}
}
p0[0]=u[a1+j][0];
p0[1]=u[a1+j][1];
p1[0]=u[c1+j][0];
p1[1]=u[c1+j][1];
p2[0]=u[b1+j][0];
p2[1]=u[b1+j][1];
a[0]=p0[0]-p1[0];
a[1]=p0[1]-p1[1];
b[0]=p2[0]-p1[0];
b[1]=p2[1]-p1[1];
ve.push_back(p0[0]+b[0]);
ve.push_back(p0[1]+b[1]);
return ve;
}
int main(){
cin>>n;
while(n--){
cin>>s>>t>>a>>b;
for(int i=1;i<=s;i++){//城市编号
for(int j=0;j<3;j++){
cin>>u[j+4*(i-1)][0]>>u[j+4*(i-1)][1];
}
//找第四个点
point=find(4*(i-1));
u[3+4*(i-1)][0]=point[0];
u[3+4*(i-1)][1]=point[1];
cin>>T[i];
//初始化铁路
for(int j=0;j<4;j++){
for(int k=0;k<4;k++){
if(j!=k)mp[j+4*(i-1)][k+4*(i-1)]=T[i]*dis(j+4*(i-1),k+4*(i-1));
else mp[j+4*(i-1)][k+4*(i-1)]=0;
}
}
}
//初始化飞机
for(int i=0;i<4*s;i++){
for(int j=0;j<4*s;j++){
if(!mp[i][j]){
mp[i][j]=t*dis(i,j);
}
}
}
for(int i=0;i<4*s;i++){
for(int j=0;j<4*s;j++){
dp[i][j]=mp[i][j];
}
}
//弗洛伊德 注意k在最外层
for(int k=0;k<4*s;k++){
for(int i=0;i<4*s;i++){
for(int j=0;j<4*s;j++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
}
}
}
//找最小值
for(int j=0;j<4;j++){
for(int k=0;k<4;k++){
ans=min(ans,dp[j+4*(a-1)][k+4*(b-1)]);
}
}
//保留一位小数
printf("%.1f",ans);
}
return 0;
}