首页 > 代码库 > luogu P1027 Car的旅行路线
luogu P1027 Car的旅行路线
题目描述
又到暑假了,住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场,分别位于一个矩形的四个顶点上,同一个城市中两个机场之间有一条笔直的高速铁路,第I个城市中高速铁路了的单位里程价格为Ti,任意两个不同城市的机场之间均有航线,所有航线单位里程的价格均为t。
图例(从上而下)
机场 高速铁路
飞机航线
注意:图中并没有
标出所有的铁路与航线。
那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题,于是她来向你请教。
找出一条从城市A到B的旅游路线,出发和到达城市中的机场可以任意选取,要求总的花费最少。
输入输出格式
输入格式:
第一行为一个正整数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行,每行一个数据对应测试数据。 保留一位小数
输入输出样例
输入样例#1:
13 10 1 31 1 1 3 3 1 302 5 7 4 5 2 18 6 8 8 11 6 3
输出样例#1:
47.5
qvkongbu:
#include <algorithm>#include <cstring>#include <cstdio>#include <cmath>#define y1 mmpusing namespace std;const int M(2333);const int N(110<<2);const double INF(1e15);int n,city_num,A,B;double dis[N][N],ans;int air_cost,road_cost[N];int x1,x2,x3,x4,y1,y2,y3,y4,d1,d2,d3;struct Node{ int x,y; Node(int x=0,int y=0): x(x),y(y) {}}airport[M];int Get_dis(int a,int aa,int b,int bb){ return (a-b)*(a-b)+(aa-bb)*(aa-bb);}void init(){ memset(dis,0,sizeof(dis)); memset(airport,0,sizeof(airport)); memset(road_cost,0,sizeof(road_cost));}int main(){ scanf("%d",&n); for(;n;n--) { init(); scanf("%d%d%d%d",&city_num,&air_cost,&A,&B); for(int i=1;i<=city_num;i++) { scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3); scanf("%d",road_cost+i); d1=Get_dis(x1,y1,x2,y2); d2=Get_dis(x2,y2,x3,y3); d3=Get_dis(x3,y3,x1,y1); if(d1>d2&&d1>d3) x4=x1+x2-x3, y4=y1+y2-y3; else if(d2>d1&&d2>d3) x4=x2+x3-x1, y4=y2+y3-y1; else if(d3>d1&&d3>d2) x4=x3+x1-x2, y4=y3+y1-y2; airport[(i<<2)-3]=Node(x1,y1); airport[(i<<2)-2]=Node(x2,y2); airport[(i<<2)-1]=Node(x3,y3); airport[(i<<2)-0]=Node(x4,y4); } for(int i=0;i<=(city_num<<2);i++) for(int j=0;j<=(city_num<<2);j++) if(i!=j) dis[i][j]=INF; for(int i=0;i<=(city_num<<2);i++) for(int j=0;j<=(city_num<<2);j++) { double dist=sqrt(Get_dis(airport[i].x,airport[i].y,airport[j].x,airport[j].y)); if(i+3>>2==j+3>>2) dis[i][j]=dist*(road_cost[i+3>>2]); else dis[i][j]=dist*air_cost; } dis[0][(A<<2)-3]=0; dis[0][(A<<2)-2]=0; dis[0][(A<<2)-1]=0; dis[0][(A<<2)-0]=0; for(int k=0;k<=(city_num<<2);k++) for(int i=0;i<=(city_num<<2);i++) for(int j=0;j<=(city_num<<2);j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); ans=min(min(dis[0][(B<<2)-3],dis[0][(B<<2)-2]),min(dis[0][(B<<2)-1],dis[0][B<<2])); printf("%.1lf\n",ans); } return 0;}
luogu P1027 Car的旅行路线
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。