「Luogu1027」Car的旅行路线

Source and Judge

NOIP2001 提高组 T4
Luogu1027
Caioj1507

Problem

「Brief description」
又到暑假了,住在城市A的Car想和朋友一起去城市B旅游。
她知道每个城市都有四个飞机场,分别位于一个矩形的四个顶点上,
同一个城市中两个机场之间有一条笔直的高速铁路,
第I个城市中高速铁路了的单位里程价格为Ti,
任意两个不同城市的机场之间均有航线,所有航线单位里程的价格均为t。

那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?
她发现这并不是一个简单的问题,于是她来向你请教。
找出一条从城市A到B的旅游路线,出发和到达城市中的机场可以任意选取,要求总的花费最少。
「Input」
第一行为一个正整数n,表示有n组测试数据。
每组的第一行有四个正整数s,t,A,B。
S表示城市的个数,t表示飞机单位里程的价格,A,B分别为城市A,B的序号。
接下来有S行,其中第I行均有7个正整数xi1,yi1,xi2,yi2,xi3,yi3,Ti,
这当中的(xi1,yi1),(xi2,yi2),(xi3,yi3)分别是第I个城市中任意三个机场的坐标,
T I为第I个城市高速铁路单位里程的价格。
「Output」
共有n行,每行一个数据对应测试数据。
保留一位小数
「Limited conditions」
0<=n<=10
0<S<=100
1<=A,B<=S
「Sample input」
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
「Sample output」
47.5
「Sample explanation」

Record

1h

Analysis1

请先思考后再展开

这就是一个复杂构图的最短路裸题
属于码农题

关于矩形的第四个点,我是自己yy出来的,写了较多注释

Code1

请先思考后再展开
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
//Zory-2018
//*******************头文件******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
#ifdef WIN32
#define BIGN "%I64d"
#else
#define BIGN "%lld"
#endif
using namespace std;
typedef long long ll;
int mymax(int x,int y) {return x>y?x:y;}
double mymin(double x,double y) {return x<y?x:y;}
//*******************全局常量****************
const int MAXN=410;
const int INF=0x3f3f3f3f;
//*******************全局定义****************
struct Nod
{
double x,y;
double d;
bool v;
Nod()
{
v=0;
}
}p[MAXN];
double cs[MAXN];
double mp[MAXN][MAXN];
//*******************实现******************
double dis(double ax,double ay,double bx,double by)
{
return sqrt( (ax-bx)*(ax-bx)+(ay-by)*(ay-by) );
}
void calc4(int x)
{
int a=4*(x-1),b=4*(x-1)+1,c=4*(x-1)+2,d=4*(x-1)+3;
double mx=(p[a].x+p[b].x)/2,my=(p[a].y+p[b].y)/2;//尝试ab
double d1=dis(mx,my,p[a].x,p[a].y),d2=dis(mx,my,p[c].x,p[c].y);
if( d1-d2<-1e-6 or d1-d2>1e-6 )//取错了,尝试ac
{
swap(b,c);
mx=(p[a].x+p[b].x)/2;my=(p[a].y+p[b].y)/2;
d1=dis(mx,my,p[a].x,p[a].y),d2=dis(mx,my,p[c].x,p[c].y);
if( d1-d2<-1e-6 or d1-d2>1e-6 )//取错了,尝试bc
{
swap(a,c);
mx=(p[a].x+p[b].x)/2;my=(p[a].y+p[b].y)/2;
d1=dis(mx,my,p[a].x,p[a].y),d2=dis(mx,my,p[c].x,p[c].y);
}
}
//a b c d
//a c b d
//b c a d
//现确保a和b为对角
p[d].x=mx*2-p[c].x;
p[d].y=my*2-p[c].y;
//p[d].x+p[c].x=mx*2
}
int lst[MAXN];
int n;
void spfa(int st)
{
int tou=1,wei=2;lst[tou]=st;
p[st].v=1;p[st].d=0;
while(tou!=wei)
{
int x=lst[tou++];
if(tou==MAXN) tou=1;
for(int j=0;j<=4*n-1;j++)
{
if(p[j].d>p[x].d+mp[x][j])
{
p[j].d=p[x].d+mp[x][j];
if(!p[j].v)
{
p[j].v=1;
lst[wei++]=j;
if(wei==MAXN) wei=1;
}
}
}
p[x].v=0;
}
}
//*******************主函数******************
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int st,ed;double s;scanf("%d%lf%d%d",&n,&s,&st,&ed);
for(int i=1;i<=n;i++)
{
for(int t1=0;t1<=2;t1++) scanf("%lf%lf",&p[4*(i-1)+t1].x,&p[4*(i-1)+t1].y);
calc4(i);scanf("%lf",&cs[i]);
}
for(int i=0;i<=4*n-1;i++)
{
for(int j=0;j<i;j++)
{
double ts=( (i/4)==(j/4) )?cs[i/4+1]:s;
mp[i][j]=mp[j][i]=dis(p[i].x,p[i].y,p[j].x,p[j].y)*ts;
}
}
double ans=INF;
for(int i=0;i<=3;i++)
{
for(int j=0;j<=4*n-1;j++) p[j].d=INF;
spfa(4*(st-1)+i);
for(int j=0;j<=3;j++) ans=mymin(ans,p[ 4*(ed-1)+j ].d);
}
printf("%.2lf\n",ans);
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/e9ee.html
转载请注明出处,谢谢!