本文主要是介绍Car的旅行路线 蓝桥真题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
蓝桥题是真的坑 样例上写的是t组数据的格式 但是测试数据根本没有t 都是单组 这不是坑人吗?
其实就是最短路裸题 建图时需要一点计算几何
对于每个矩形只给任意三个顶点 利用向量点乘判断直角点
假设 1和3 2和4 互为对角点 那就满足 x1+x3=x2+x4 且 y1+y3=y2+y4 以此求出最后一个点
#include <bits/stdc++.h>
using namespace std;
#define eps 1e-8
#define N 10000000000000000000000.0struct node1
{double x;double y;
};struct node2
{bool friend operator < (node2 n1,node2 n2){return n1.val>n2.val;}double val;int id;
};priority_queue <node2> que;
node1 point[410];
double e[410][410];
double pre[110],dis[410];
double c;
int book[410];
int n;double cal(int u,int v)
{return sqrt(pow(point[u].x-point[v].x,2)+pow(point[u].y-point[v].y,2));
}double dijkstra(int ss,int ee)
{node2 cur,tem;double w;int i,u,v;while(!que.empty()) que.pop();for(i=0;i<n;i++){dis[i]=N;book[i]=0;}tem.id=ss,tem.val=0.0;que.push(tem);dis[ss]=0.0;while(!que.empty()){cur=que.top();que.pop();u=cur.id;if(book[u]) continue;book[u]=1;for(v=0;v<n;v++){if(u!=v&&!book[v]){w=e[u][v];if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;tem.id=v,tem.val=dis[v];que.push(tem);}}}}return min(min(dis[4*ee],dis[4*ee+1]),min(dis[4*ee+2],dis[4*ee+3]));
}int main()
{double x1,y1,x2,y2,x3,y3,x4,y4,ans;int ss,ee,i,j;while(scanf("%d%lf%d%d",&n,&c,&ss,&ee)!=EOF){ss--,ee--;for(i=0;i<n;i++){scanf("%lf%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3,&pre[i]);if(fabs((x2-x1)*(x3-x2)+(y2-y1)*(y3-y2))<eps)//2{x4=x1+x3-x2;y4=y1+y3-y2;}else if(fabs((x3-x2)*(x1-x3)+(y3-y2)*(y1-y3))<eps)//3{x4=x1+x2-x3;y4=y1+y2-y3;}else//1{x4=x2+x3-x1;y4=y2+y3-y1;}point[4*i].x=x1,point[4*i].y=y1;point[4*i+1].x=x2,point[4*i+1].y=y2;point[4*i+2].x=x3,point[4*i+2].y=y3;point[4*i+3].x=x4,point[4*i+3].y=y4;}n*=4;for(i=0;i<n;i++){for(j=0;j<n;j++){if(i/4==j/4){e[i][j]=cal(i,j)*pre[i/4];}else{e[i][j]=cal(i,j)*c;}}}ans=N;for(i=0;i<4;i++){ans=min(ans,dijkstra(4*ss+i,ee));}printf("%.1f\n",ans);}return 0;
}
这篇关于Car的旅行路线 蓝桥真题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
