洛谷1027 Car的旅行路线

题面

  • 安利一发Blog,不点进来看下吗??
  • 这道题可以说很很很很恶心了ヽ(#`Д´)ノ,恶心的是建图。本来想抄的题解的,但是题解里面$Floyd$的题解不是特别详细,关键是不符合我的码风!!所以还是自己敲了个​(很丑的)$Floyd$。难度应该是绿题吧,我觉得,但是蓝题也不是特别夸张(逃
  • 该题还有一个难点就是找一个城市中的第4个点,用勾股定理判断直角三角形的直角,从而判断第4个点。(题目中说了4个飞机场围成矩形哦~~)
  • 最后说一个做题技巧:碰到繁琐的题目要多封装韩硕,不然会把自己弄晕的,也不好$Debug$~~
  • Code:很多细节在代码中哦~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#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,发现有问题请私信我~~
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×