本文共 2211 字，大约阅读时间需要 7 分钟。
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1245
题意：给一个已知直径的圆形岛，然后岛的附近是湖，湖里有一些点，以坐标的形式给出，最外层是矩形的终点。
给定跳跃的距离d,让你判断是否能跳到最外层，如果能就输出最短距离以及这个最短跳的步数。
题解：
这题重点在建图，在松弛操作那里也要修改一下。详细看代码。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #define cl(a,b) memset(a,b,sizeof(a));12 #define FFC(i,a,b) for(int i=a;i<=b;i++)13 #define FFI(i,a,b) for(int i=a;i>=b;i--)14 #define pb push_back15 #define LL long long16 using namespace std;17 void fre(){freopen("c:\\acm\\input.txt","r",stdin);}18 const double INF=1e9,eps=1e-5;19 const int MAXN=110,MAXM=11000;20 typedef pair P;21 priority_queue ,greater >Q;22 int v[MAXM],g[MAXN],nxt[MAXM],ed,i,x,N,pre[MAXN];23 double w[MAXM],d[MAXN];24 int n,xx,yy,cnt,K;25 void init(int n){ for(i=1,ed=0,N=n;i<=n;i++)g[i]=0;}26 void adg(int x,int y,double z){v[++ed]=y,w[ed]=z,nxt[ed]=g[x],g[x]=ed;}27 void dijkstra(int S){28 for(i=1;i<=N;i++)d[i]=INF,pre[i]=S;Q.push(P(d[S]=0,S));29 while(!Q.empty()){30 P t=Q.top();Q.pop();31 if(t.first>d[x=t.second])continue;32 for(i=g[x];i;i=nxt[i])if(d[x]+w[i] K)){ //距离必须小于K才能跳33 pre[v[i]]=x;//记录路径34 Q.push(P(d[v[i]]=d[x]+w[i],v[i]));35 }36 }37 }38 struct dt{39 int x,y;40 }a[110];41 int abs(int a){ return a eps){adg(1,i,tmp-7.5);adg(i,1,tmp-7.5);}49 }50 FFC(i,2,cnt)FFC(j,i,cnt){51 if(i==j){adg(i,j,0);adg(j,i,0);}52 else{53 double tmp=getdis(a[i].x,a[i].y,a[j].x,a[j].y);54 adg(i,j,tmp);55 adg(j,i,tmp);56 }57 }58 //cnt+1为终点59 FFC(i,2,cnt){60 int min=(50-abs(a[i].x))>(50-abs(a[i].y))?(50-abs(a[i].y)):(50-abs(a[i].x));61 adg(cnt+1,i,(double)min);62 adg(i,cnt+1,(double)min);63 }64 }65 int getlong(){66 int an=0,i=cnt+1;67 while(pre[i]!=i){68 i=pre[i],an++;69 }70 return an;71 }72 int main(){73 //fre();74 while(~scanf("%d%d",&n,&K)){75 cnt=1;76 FFC(i,1,n){77 scanf("%d%d",&xx,&yy);78 if(xx<50&&yy<50)a[++cnt].x=xx,a[cnt].y=yy;79 }80 //特判，如果K大于42.5可一步跳到岸边81 if(K>=42.5){printf("42.50 1\n");continue;}82 init(cnt+1);83 build_g();//建图84 dijkstra(1);85 double ans=d[cnt+1];86 if(ans
,greater
>Q;22 int v[MAXM],g[MAXN],nxt[MAXM],ed,i,x,N,pre[MAXN];23 double w[MAXM],d[MAXN];24 int n,xx,yy,cnt,K;25 void init(int n){ for(i=1,ed=0,N=n;i<=n;i++)g[i]=0;}26 void adg(int x,int y,double z){v[++ed]=y,w[ed]=z,nxt[ed]=g[x],g[x]=ed;}27 void dijkstra(int S){28 for(i=1;i<=N;i++)d[i]=INF,pre[i]=S;Q.push(P(d[S]=0,S));29 while(!Q.empty()){30 P t=Q.top();Q.pop();31 if(t.first>d[x=t.second])continue;32 for(i=g[x];i;i=nxt[i])if(d[x]+w[i]
转载于:https://www.cnblogs.com/bin-gege/p/5696190.html
