car的旅行路线
这个题关键就是
如何把每个点表示出来,其实求出四个点的坐标后,只需要把这些点连接起来,用一遍folyed求出最短路径就好了。
代码:
#include<cmath>
#include<cstdio>
int x[],y[];//x表示横坐标,y表示纵坐标
int ti[];//在第i个城市中铁路单位里程价格
int n,s,tt,a,b;//tt表示航线单位里程价格
double d[][];//i到j的长度(花费)
void doit(int t1,int t2){//计算t1到t2的花费
d[t1][t2]=sqrt((x[t1]-x[t2])*(x[t1]-x[t2])
+(y[t1]-y[t2])*(y[t1]-y[t2]));//求t1到t2的长度
if (((t1-)/)==((t2-)/)){//判断t1,t2是否在同一个城市内
d[t1][t2]=d[t1][t2]*ti[(t1-)/+];//计算花费
}else
d[t1][t2]=d[t1][t2]*tt;
d[t2][t1]=d[t1][t2];//对称
return;//结束
}
int find(int t1,int t2,int t3){//找直角三角形斜边
//如果一边长度大于任意两边返回此边对着的点
if((d[t1][t2]>d[t2][t3])&&(d[t1][t2]>d[t3][t1])) return t3;
//t1t2对应的点为t3
if((d[t2][t3]>d[t1][t2])&&(d[t2][t3]>d[t3][t1])) return t1;
//t2t3对应的点为t1
if((d[t3][t1]>d[t2][t3])&&(d[t3][t1]>d[t1][t2])) return t2;
//t1t3对应的点为t2
}
void doit2(int t1,int t2,int t3){
doit(t1,t2);//t1到t2的花费(比在同一城市)
doit(t2,t3);//t2到t3的花费(必在同一城市)
doit(t3,t1);//t3到t1的花费(必在同一城市)
int haha=find(t1,t2,t3);//找此直角三角形的斜边
//而在平行四边形中
//一条边的两个顶点的横(或纵)坐标的差值
//等于其对边两个顶点的横(或纵)坐标的差值
if(haha==t1){//看斜边对着的点为哪个,并求出第4个点的坐标
x[t3+]=x[t3]+x[t2]-x[t1];
y[t3+]=y[t3]+y[t2]-y[t1];
}
else if(haha==t2){
x[t3+]=x[t3]+x[t1]-x[t2];
y[t3+]=y[t3]+y[t1]-y[t2];
}
else if(haha==t3){
x[t3+]=x[t1]+x[t2]-x[t3];
y[t3+]=y[t1]+y[t2]-y[t3];
}
}
int main(){
scanf("%d",&n);
for(;n>=;n--){//循环运行n次
scanf("%d %d %d %d",&s,&tt,&a,&b);
//S城市数,t飞机单价,A,B序号
int i,j,k;
for(i=;i<=;i++)//初始化
for(j=;j<=;j++)
d[i][j]=;
for(i=;i<=s;i++){
scanf("%d%d%d%d%d%d%d",
&x[*i-],&y[*i-],&x[*i-],
&y[*i-],&x[*i-],&y[*i-],
&ti[i]);
doit2(*i-,*i-,*i-);
}
for(i=;i<=*s;i++)
for(j=;j<=*s;j++)
doit(i,j);//计算i到j的花费
for(k=;k<=*s;k++)
for(i=;i<=*s;i++)
for(j=;j<=*s;j++)
if(d[k][j]+d[i][k]<d[i][j])
d[i][j]=d[k][j]+d[i][k];//Floyed
double ans=200000000.0;
for(i=*a-;i<=*a;i++)
for(j=*b-;j<=*b;j++)
if(d[i][j]<ans)
ans=d[i][j];//更新最小值
printf("%.1lf\n",ans);//输出,并保留一位小数
}
return ;
}