题解 P1027 【Car的旅行路线】

这道题代码可真的不简单。。 ## 题目链接： https://www.luogu.org/problem/P1027 ## 分析： **注：这里面的点指机场而非城市** 这道题乍一看题目描述不难，其实就是一个最短路问题，不过就是起点可能有多个，终点也有多个，所以我们跑个Floyd就行。 - 但因为我怕$O(n^3)$跑不起，所以换成了$n$遍$dijkstra$(这里n☞点数) 所以时间复杂度为：$O(n^2log_n)$ - (dij用了堆优化 ### 然后我们来到样例，发现还有毒瘤的预处理。 样例无良的给了矩形的三个点，说明第四个点可以根据前三个求出。 - 于是我们考虑到运用矩形对角线的一些性质。 - 首先找出距离最远的两个点（三个点中） - 然后连线取中点（当然编程中不用连线那一步操作） - 再将另外的第3个点（不在连线的两端）向中点连线，延长即可 ```cpp void find(double a,double b,double c,double d,double e,double f)//读入三个点的坐标，跑完函数就把第四个点的值赋完了 { cnt++; dis[1].num=sqrt(Sqr(a-c)+Sqr(b-d)); dis[1].id=1; dis[2].num=sqrt(Sqr(e-c)+Sqr(f-d)); dis[2].id=2; dis[3].num=sqrt(Sqr(a-e)+Sqr(b-f)); dis[3].id=3; sort(dis+1,dis+4,cmp); if(dis[1].id==1) { double x=min(a,c)+Abs(a-c)/2; double y=min(b,d)+Abs(b-d)/2; double xn=x+x-e; double yn=y+y-f; p[cnt].x=xn; p[cnt].y=yn; } if(dis[1].id==2) { double x=min(c,e)+Abs(e-c)/2; double y=min(f,d)+Abs(f-d)/2; double xn=x+x-a; double yn=y+y-b; p[cnt].x=xn; p[cnt].y=yn; } if(dis[1].id==3) { double x=min(a,e)+Abs(a-e)/2; double y=min(b,f)+Abs(b-f)/2; double xn=x+x-c; double yn=y+y-d; p[cnt].x=xn; p[cnt].y=yn; } } ``` 这样，就处理完了，最后，我们发现其实任意两点都有连接（要不航线要不铁路），所以处理出距离，在判断是否在一个城市，就可以找到每条路的价值。 - 跑dij即可 - 别忘了给点所在的城市打标记，这样最后方便找A和B **这里引申出了一个惨痛的教训：结构体的存储方式要想好** 刚开始我是以一个城市为一个结构体，然后就特别难写，最后只好重构代码 ## $code:$ ```cpp #include<cstdio> #include<cmath> #include<map> #include<cstring> #include<queue> #include<algorithm> using namespace std; #define pa pair<double,int> int vis[4005]; priority_queue<pa,vector<pa>,greater<pa> > q; struct point { double x,y,T; int id; }p[4005]; struct D { double id; double num; }dis[4]; double Sqr(int x) { return x*x; } double cmp(const D &a,const D &b) { return a.num>b.num; } double Abs(double x) { if(x<0)return -x; return x; } int cnt=0; void find(double a,double b,double c,double d,double e,double f) { cnt++; dis[1].num=sqrt(Sqr(a-c)+Sqr(b-d)); dis[1].id=1; dis[2].num=sqrt(Sqr(e-c)+Sqr(f-d)); dis[2].id=2; dis[3].num=sqrt(Sqr(a-e)+Sqr(b-f)); dis[3].id=3; sort(dis+1,dis+4,cmp); if(dis[1].id==1) { double x=min(a,c)+Abs(a-c)/2; double y=min(b,d)+Abs(b-d)/2; double xn=x+x-e; double yn=y+y-f; p[cnt].x=xn; p[cnt].y=yn; } if(dis[1].id==2) { double x=min(c,e)+Abs(e-c)/2; double y=min(f,d)+Abs(f-d)/2; double xn=x+x-a; double yn=y+y-b; p[cnt].x=xn; p[cnt].y=yn; } if(dis[1].id==3) { double x=min(a,e)+Abs(a-e)/2; double y=min(b,f)+Abs(b-f)/2; double xn=x+x-c; double yn=y+y-d; p[cnt].x=xn; p[cnt].y=yn; } } double d[405][405],dist[405][405]; void dijkstra(int s) { memset(vis,0,sizeof(vis)); d[s][s]=0; q.push(make_pair(0,s)); while(!q.empty()) { int x=q.top().second; q.pop(); if(vis[x]==1) continue; vis[x]=1; for(int i=1;i<=cnt;i++) { if(d[s][x]+dist[x][i]<d[s][i]) { d[s][i]=d[s][x]+dist[x][i]; q.push(make_pair(d[s][i],i)); } } } } int main() { double t; int N,A,B,s; scanf("%d",&N); while(N--) { cnt=0; scanf("%d%lf%d%d",&s,&t,&A,&B); int city=0; for(int i=1;i<=s;i++) { city++; for(int j=1;j<=3;j++) { cnt++; scanf("%lf%lf",&p[cnt].x,&p[cnt].y); p[cnt].id=city; } scanf("%lf",&p[cnt].T); p[cnt-2].T=p[cnt].T; p[cnt-1].T=p[cnt].T; p[cnt+1].T=p[cnt].T; //printf("%lf %lf\n",p[cnt-j+1].x,p[cnt-j+1].y); find(p[cnt-2].x,p[cnt-2].y,p[cnt-1].x,p[cnt-1].y,p[cnt].x,p[cnt].y); p[cnt].id=city; //printf("i=%lf %lf\n",p[cnt].x,p[cnt].y); } for(int i=1;i<=cnt;i++) { for(int j=1;j<=cnt;j++) { double tmp=sqrt(Sqr(p[i].x-p[j].x)+Sqr(p[i].y-p[j].y)); if(p[i].id==p[j].id) { dist[i][j]=tmp*p[i].T; } else { dist[i][j]=tmp*t; } } } for(int i=1;i<=cnt;i++) { for(int j=1;j<=cnt;j++) { d[i][j]=2147483640; } } for(int i=1;i<=cnt;i++) { dijkstra(i); } double ans=2147483640; for(int i=1;i<=cnt;i++) { for(int j=1;j<=cnt;j++) { if(p[i].id==A&&p[j].id==B) { if(d[i][j]<ans) { ans=d[i][j]; } //ans=min(ans,d[i][j]); } } } printf("%.1lf\n",ans); } return 0; } ```