首页 > 代码库 > poj 2627 Gopher and hawks 最短路
poj 2627 Gopher and hawks 最短路
题意:
给老鼠的速度v和移动时老鼠在洞外的最长时间m、地面上n个点的坐标,问老鼠是否可以从洞1到洞2,可以的话求最少跳数。
分析:
裸的最短路,注意精度。
代码:
//poj 2627 //sep9 #include <iostream> #include <queue> using namespace std; const int maxN=1024; const int maxM=2000024; int n,e,head[maxN]; int d[maxN]; int inq[maxN]; struct Point { __int64 x,y; }pnt[1024]; __int64 v,m; struct Edge { int v,w,nxt; }edge[maxM]; void addedge(int u,int v,int w) { edge[e].v=v;edge[e].w=w;edge[e].nxt=head[u];head[u]=e++; edge[e].v=u;edge[e].w=w;edge[e].nxt=head[v];head[v]=e++; } queue<int> Q; void spfa() { for(int i=0;i<n;++i) d[i]=INT_MAX; memset(inq,0,sizeof(inq)); d[0]=0; Q.push(0); inq[0]=1; while(!Q.empty()){ int u=Q.front();Q.pop();inq[u]=0; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].v,w=edge[i].w; if(d[u]+w<d[v]){ d[v]=d[u]+w; if(!inq[v]){ inq[v]=1; Q.push(v); } } } } } int main() { e=0; memset(head,-1,sizeof(head)); scanf("%I64d%I64d",&v,&m); m*=60; double x,y; n=0; while(scanf("%lf%lf",&x,&y)==2){ pnt[n].x=(__int64)(x*1000.0+1e-6); pnt[n].y=(__int64)(y*1000.0+1e-6); ++n; } int i,j; for(i=0;i<n;++i) for(j=i+1;j<n;++j){ __int64 dis=(pnt[i].x-pnt[j].x)*(pnt[i].x-pnt[j].x)+(pnt[i].y-pnt[j].y)*(pnt[i].y-pnt[j].y); if(dis<=v*m*v*m*1000000) addedge(i,j,1); } spfa(); if(d[1]==INT_MAX) printf("No."); else printf("Yes, visiting %d other holes.",d[1]-1); return 0; }
poj 2627 Gopher and hawks 最短路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。