题目描述
又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第I个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。
标出所有的铁路与航线。
那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题，于是她来向你请教。
任务
找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。
输出：到屏幕(输出最小费用，小数点后保留2位。)
输入格式
第一行为一个正整数n(0<=n<=10)，表示有n组测试数据。
每组的第一行有四个正整数s，t，A，B。
S(0<S<=100)表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B的序号，(1<=A，B<=S)。
接下来有S行，其中第I行均有7个正整数xi1，yi1，xi2，yi2，xi3，yi3，Ti，这当中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分别是第I个城市中任意三个机场的坐标，T I为第I个城市高速铁路单位里程的价格。
输出格式
共有n行，每行一个数据对应测试数据。(小数点保留2位)[RQ已经订正本题目]
样例输入
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.55
#include <iostream>
#include <string>
#include <math.h>
#define MAXN 105
#define MAXM 550
#define MAX 9999999.999
typedef struct point p;
double map[MAXM][MAXM];
struct point
{
double x,y;
};
struct node
{
p *a;
p *b;
p *c;
p *d;
double T;//用来表示这里地铁每单位距离的价格
}citys[MAXN];
p* qD(p* a,p* b,p* c) //用来求第四个点
{
struct point *p4;
p4 = (struct point *)malloc(sizeof(struct point));
double x4,y4;
double centerX,centerY;
//求出三点的向量
double xAB = a->x - b->x;
double yAB = a->y - b->y;
double xAC = a->x - c->x;
double yAC = a->y - c->y;
double xBC = b->x - c->x;
double yBC = b->y - c->y;
if(xAB * xAC + yAB * yAC == 0)
{
centerX = b->x+c->x;
centerY = b->y+c->y;
x4 = centerX - a->x;
y4 = centerY - a->y;
}
else if(xAB * xBC + yAB * yBC == 0)
{
centerX = a->x+c->x;
centerY = a->y+c->y;
x4 = centerX - b->x;
y4 = centerY - b->y;
}
else if(xAC * xBC + yAC * yBC== 0)
{
centerX = a->x+b->x;
centerY = a->y+b->y;
x4 = centerX - c->x;
y4 = centerY - c->y;
}
else
{
printf("Creat Point ERROR!!!");
exit(-1);
}
p4->x = x4;
p4->y = y4;
return p4;
}
double moneyWast(p *a,p* b,double T)
{
return T*sqrt(pow((a->x - b->x),2)+ pow((a->y - b->y),2));
}
void doIt(int s,double t,int A,int B)
{
int i,j,k;
double x1,y1,x2,y2,x3,y3,x4,y4;
int shangOne,shangTwo,ysOne,ysTwo;
int cur;
double min = MAX;
struct point *pp1,*pp2;
double T;//存价格
for(i=1;i <= s;i ++)
{
scanf("%lf %lf %lf %lf %lf %lf %lf",&x1,&y1,&x2,&y2,&x3,&y3,&T);
citys[i].a = (struct point *)malloc(sizeof(struct point));
citys[i].b = (struct point *)malloc(sizeof(struct point));
citys[i].c = (struct point *)malloc(sizeof(struct point));
citys[i].a->x = x1;
citys[i].a->y = y1;
citys[i].b->x = x2;
citys[i].b->y = y2;
citys[i].c->x = x3;
citys[i].c->y = y3;
citys[i].d = qD(citys[i].a,citys[i].b,citys[i].c);
citys[i].T = T;
}
for(i=1;i <= s*4;i ++)
{
for(j=1;j <= s*4;j ++)
{
if(i == j)
{
map[i][j] = 0;
}
else
{
shangOne = i/4+1;
shangTwo = j/4+1;
ysOne = i%4;
ysTwo = j%4;
if(ysOne == 0)
{
shangOne --;
ysOne = 4;
}
if(ysTwo == 0)
{
shangTwo --;
ysTwo = 4;
}
switch(ysOne)
{
case 1:
pp1 = citys[shangOne].a;
break;
case 2:
pp1 = citys[shangOne].b;
break;
case 3:
pp1 = citys[shangOne].c;
case 4:
pp1 = citys[shangOne].d;
break;
default:
printf("ERROR!!");
break;
}
switch(ysTwo)
{
case 1:
pp2 = citys[shangTwo].a;
break;
case 2:
pp2 = citys[shangTwo].b;
break;
case 3:
pp2 = citys[shangTwo].c;
break;
case 4:
pp2 = citys[shangTwo].d;
break;
default:
printf("ERROR!!");
break;
}
if(shangOne == shangTwo)//说明他们两个在同一个城市里可以坐火车到达
{
map[i][j] = moneyWast(pp1,pp2,citys[shangOne].T);
}
else//坐飞机到达
{
map[i][j] = moneyWast(pp1,pp2,t);
}
}
}
}
//Floyd
for(k=1;k <= s*4;k ++)
{
for(i=1;i <= s*4;i ++)
{
for(j=1;j <= s*4;j ++)
{
if(i != j && i != k && j != k && map[i][j] > map[i][k] + map[k][j])
{
map[i][j] = map[i][k] + map[k][j];
}
}
}
}
//选出最小的费用
for(i=A*4-3;i <= A*4;i ++)
{
for(j=B*4-3;j <= B*4;j ++)
{
if(map[i][j] < min)
{
min = map[i][j];
}
}
}
printf("%0.1lf\n",min);
}
int main()
{
freopen("Test.in","r",stdin);
freopen("Test.out","w",stdout);
int i;
int n;
int s,A,B;
double t;
scanf("%d",&n);
for(i=1;i <= n;i ++)
{
scanf("%d %lf %d %d",&s,&t,&A,&B);
doIt(s,t,A,B);
}
}
可以过4个点，一共是5个点
样例数据就是过不了，最后一个点的答案也是错误的
求解啊！！！各位大牛！！
[课程]Linux pwn 探索篇！
好了 应该差不多要动了....好久不看算法，感觉都没了....
