题解 P1027 【Car的旅行路线】
Snowflake_Pink
2019-02-07 11:59:46
## [题面](https://www.luogu.org/problemnew/show/P1027)
* **安利一发[Blog](https://www.17shou.vip/),不点进来看下吗??**
* 这道题可以说很很很很恶心了ヽ(#`Д´)ノ,恶心的是建图。~~本来想抄的题解的,~~但是题解里面$Floyd$的题解不是特别详细,~~关键是不符合我的码风!!~~所以还是自己敲了个(很丑的)$Floyd$。难度应该是绿题吧,我觉得,~~但是蓝题也不是特别夸张(逃~~
* 该题还有一个难点就是找一个城市中的第4个点,用勾股定理判断直角三角形的直角,从而判断第4个点。(题目中说了4个飞机场围成矩形哦~~)
* 最后说一个做题技巧:碰到繁琐的题目要多封装韩硕,不然会把自己弄晕的,也不好$Debug$~~
* Code:很多细节在代码中哦~
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define INF 999999999
using namespace std;
struct Point{
int x,y;
}p[105];//各个飞机场的坐标
int T,t,s,n,A,B,cnt;//定义:飞机费用、铁路费用、城市个数s、n组数据、A出发点、B目的地、飞机场个数
int textx[5],texty[5];//临时数组
double g[1005][1005],ans;//邻接数组储存图、ans答案
void Init(){//程序初始化
memset(p,0,sizeof(p));
for (int i=1;i<=1000;i++)
for (int j=1;j<=1000;j++)
if (i!=j) g[i][j]=INF;
else g[i][j]=0;
cnt=0;
t=0;
ans=INF;
return;
}
void Get(){//利用勾股定理,计算第4个点
int ab=(textx[1]-textx[2])*(textx[1]-textx[2])+(texty[1]-texty[2])*(texty[1]-texty[2]);
int ac=(textx[1]-textx[3])*(textx[1]-textx[3])+(texty[1]-texty[3])*(texty[1]-texty[3]);
int bc=(textx[2]-textx[3])*(textx[2]-textx[3])+(texty[2]-texty[3])*(texty[2]-texty[3]);
if (ab+ac==bc) textx[4]=textx[2]+textx[3]-textx[1],texty[4]=texty[2]+texty[3]-texty[1];
if (ab+bc==ac) textx[4]=textx[1]+textx[3]-textx[2],texty[4]=texty[1]+texty[3]-texty[2];
if (ac+bc==ab) textx[4]=textx[1]+textx[2]-textx[3],texty[4]=texty[1]+texty[2]-texty[3];
return;
}
void addEdge(int a,int b,int x[],int y[]){//添加铁路线
int ta=a+cnt;
int tb=b+cnt;
p[ta].x=x[a];
p[ta].y=y[a];
p[tb].x=x[b];
p[tb].y=y[b];
if (g[ta][tb]!=INF) return;//如果算过就不算了
g[ta][tb]=sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]))*t;
g[tb][ta]=g[ta][tb];
return;
}
void addFlight(int a,int b){
if (g[a][b]!=INF) return;//如果以前算过(包括铁路线),就不算了,保证飞机线不会算到铁路线去
g[a][b]=sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y))*T;
g[b][a]=g[a][b];
return;
}
void Floyd(){//最短路计算
for (int k=1;k<=cnt;k++)
for (int i=1;i<=cnt;i++)
for (int j=1;j<=cnt;j++)
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
return;
}
int main(){
scanf("%d",&n);
while(n--){
Init();
scanf("%d%d%d%d",&s,&T,&A,&B);
for (int i=1;i<=s;i++){
scanf("%d%d%d%d%d%d%d",&textx[1],&texty[1],&textx[2],&texty[2],&textx[3],&texty[3],&t);
Get();
for (int j=1;j<=4;j++)
for (int k=1;k<=4;k++)
if (j!=k) addEdge(j,k,textx,texty);
cnt+=4;
}
for (int i=1;i<=cnt;i++)
for (int j=1;j<=cnt;j++)
addFlight(i,j);
Floyd();
for (int i=A*4-3;i<=A*4;i++)
for (int j=B*4-3;j<=B*4;j++)
ans=min(ans,g[i][j]);//枚举最短费用
printf("%.1lf\n",ans);
}
return 0;
}
```
* PS:代码写太丑了QAQ,发现有问题请私信我~~