题解 P1027 【Car的旅行路线】

Snowflake_Pink

2019-02-07 11:59:46

Solution

## [题面](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,发现有问题请私信我~~