首页 > 代码库 > HDU 4885 TIANKENG’s travel 最短路
HDU 4885 TIANKENG’s travel 最短路
判断是否共线用map记录下斜率;
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <limits.h> #include<algorithm> #include<math.h> #include<map> using namespace std; #define N 1022 const int INF = 1<<30-1; bool vis[2020]; int mat[1022][1022],lowcost[1022],pre[1033]; double cost[1022][1022]; int maxlong,star,end; double mathh(int a,int c,int b,int d) { return sqrt((a-b)*(a-b)*1.0+(c-d)*(c-d)*1.0); } double xielv(int a,int c,int b,int d) { if(a==b)//垂直x轴 return INF; else return (d-c)*1.0/(b-a); } struct node { int x,y; } point[1022]; bool cmp(node a,node b) { if(a.x==b.x) return a.y<b.y; return a.x<b.x; } struct node1 { int star,step; }; void Dijkstra(int n,int beg) { for(int i=0; i<n; i++) { lowcost[i]=INF; vis[i]=false; pre[i]=-1; } lowcost[beg]=0; for(int j=0; j<n; j++) { int k=-1; int Min=INF; for(int i=0; i<n; i++) if(!vis[i]&&lowcost[i]<Min) { Min=lowcost[i]; k=i; } if(k==-1)break; vis[k]=true; for(int i=0; i<n; i++) if(!vis[i]&&lowcost[k]+mat[k][i]<lowcost[i]) { lowcost[i]=lowcost[k]+mat[k][i]; pre[i]=k; } } } int main() { int n,t; // freopen("in.txt","r",stdin); scanf("%d",&t); while(t--) { memset(mat,0,sizeof(mat)); memset(cost,0,sizeof(cost)); scanf("%d%d",&n,&maxlong); for(int i=0; i<n+2; i++) scanf("%d%d",&point[i].x,&point[i].y); int a=point[1].x,b=point[1].y; int c=point[0].x,d=point[0].y; sort(point,point+n+2,cmp); for(int i=0; i<n+2; i++) //找到起点和终点 { if(a==point[i].x&&b==point[i].y) end=i; if(c==point[i].x&&d==point[i].y) star=i; } for(int i=0; i<n+2; i++)//计算距离 for(int j=0 ; j<n+2; j++) cost[i][j]=mathh(point[i].x,point[i].y,point[j].x,point[j].y); for(int i=0; i<n+2; i++) { map<double ,int > m; m.clear(); for(int j=i+1; j<n+2; j++)//i点开始与j点的斜率 { if(cost[i][j]<=maxlong)//先判断距离 { double xie=xielv(point[i].x,point[i].y,point[j].x,point[j].y); if(m.find(xie)==m.end())//斜率先前没出现过 { mat[i][j]=mat[j][i]=1; m[xie]=1; } else mat[i][j]=mat[j][i]=INF; } else mat[i][j]=mat[j][i]=INF; } } Dijkstra(n+2,star);//最短路 if(lowcost[end]==INF)//没有走到终点 printf("impossible\n"); else printf("%d\n",lowcost[end]-1);//走到终点的那一步不是加油站要-1; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。