大致题意:
给出一个100*100的池塘,池塘中心位于二维坐标原点。池塘中心有一个直径为15的圆形岛屿,一个人站在岛屿上。给出池塘中n个小岛的位置和这个人的最大步长。求这个人想到池塘对岸的话最少要走多长的距离,最少要迈多少步。
大致思路:
把小岛抽象为起点,对岸抽象为终点,求最短路即可。最短路的思路很好想到,但是需要精度控制的经验啊。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<fstream>
#include<cstring>
using namespace std;
const int nMax=100050;
const int mMax=1000050;
const int inf=1<<30;
const double eps=1e-12;
struct{
int v, next;
double w;
}edge[mMax];
int n,k,edgeHead[nMax];
double dis[nMax];
int stack[nMax],m;
bool vis[nMax];
int steps[nMax];
void addedge(int a,int b,double w){
edge[k].w = w;
edge[k].v=b;
edge[k].next=edgeHead[a];
edgeHead[a]=k;k++;
}
int spfa(int s){
int i, top = 0;
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++){
dis[i]=inf;
steps[i]=inf;
}
dis[s]=steps[s]=0;
stack[++top]=s;
vis[s]=true;
while(top){
int u=stack[top--];
vis[u]=false; /////////////////
for(i=edgeHead[u];i!=0;i=edge[i].next){
int v=edge[i].v;
if(abs(dis[v]-(dis[u]+edge[i].w))<=eps){
if(steps[v]>steps[u]+1){
steps[v]=steps[u]+1;
if(!vis[v]){
vis[v]=true;
stack[++top]=v;
}
}
continue;
}
if(dis[v]>dis[u]+edge[i].w){
dis[v]=dis[u]+edge[i].w;
steps[v]=steps[u]+1;
if(!vis[v]){
vis[v]=true;
stack[++top] = v;
}
}
}
}
int sum=0;
for(i=1;i<=n;i++){
sum+=dis[i];
}
return sum;
}
class fuck{
public:
int x,y;
}node[nMax];
int len;
double getdis(int a,int b){
return sqrt((node[a].x-node[b].x)*(node[a].x-node[b].x)+(node[a].y-node[b].y)*(node[a].y-node[b].y));
}
int main(){
int i,j,s,t;
double d,e;
node[0].x=node[0].y=0;
// freopen("gift.in","r",stdin);
while(scanf("%d%d",&n,&len)!=EOF){
k=1;
memset(edgeHead,0,sizeof(edgeHead));
for(i=1;i<=n;i++){
scanf("%d%d",&node[i].x,&node[i].y);
}
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(i==j)continue;
d=getdis(i,j);
// cout<<d<<endl;
if(d<=len){
addedge(i,j,d);
}
}
}
s=n+1;
t=n+2;
for(i=1;i<=n;i++){
d=getdis(0,i)-7.5;
if(d<=len){
addedge(s,i,d);
}
d=min(50-node[i].x,50-node[i].y);
e=min(node[i].x+50,node[i].y+50);
d=min(d,e);
if(d<=len){
addedge(i,t,d);
}
}
n+=2;
spfa(s);
if(fabs(dis[t]-inf)<=eps){
printf("can't be saved\n");
continue;
}
printf("%.2f %d\n",dis[t],steps[t]);
}
return 0;
}
分享到:
相关推荐
SPFA import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class SPFA { static SE[] e = new SE[9999]; static int[] dis = new int[9999]; ...
最短路无向图spfa+slm优化,可作为模板使用
SPFA算法模版+邻接表实现.docx
SPFA——Shortest Path Faster Algorithm,它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径,可以处理负边。
求单源最短路的SPFA算法的全称是:Shortest Path Faster Algorithm。 这个是自己写的,思想还是一样发的。
这里是SPFA的源代码
SPFA[知乎:叶枝黎曼].py
最短路SPFA算法。SPFA(Shortest Path Faster Algorithm)算法是求单源最短路径的一种算法,它是Bellman-ford的队列优化,它是一种十分高效的最短路算法。存在负权边时使用。
自己打的spfa算法板子。包含邻接表的两种形式,邻接矩阵Map;此代码不完全,(使用是要注释掉部分的)在使用时要结合题意更改。望采纳!
SPFA算法优化及应用,SPFA算法优化及应用,SPFA算法优化及应用
求单源最短路的SPFA算法的全称是:Shortest Path Faster Algorithm。 SPFA算法是西南交通大学段凡丁于1994年发表的. 从名字我们就可以看出,这种算法在效率上一定有过人之处。 很多时候,给定的图存在负权边,这时...
spfa算法的java实现
SPFA算法,acm常用的算法,求最短路径
这个是关于SPFA最短路径一些相关东西。。
最短路课件(链式前向星+堆优化+SPFA)
求单源最短路的SPFA算法的全称是:Shortest Path Faster Algorithm。 从名字我们就可以看出,这种算法在效率上一定有过人之处。
spfa模板,双向图的,但是里面也有介绍改成单向图的。 实际是freepascal的,但是没有分类,只好放到C/C++分类里了,希望能帮到大家
基本思想 用一个队列来进行维护。初始时将源加入队列。每次从队列中取出一个元素,并对所有与他相邻的点进行松弛,若某个相邻的点松弛成功,则将其入队。直到队列为空时算法结束; 利用了每个点不会更新次数太多的...
SPFA算法就解决了重复计算的问题,在大数据面前大大减少运行时间 该算法改善的思想是避免顶点进行无效的重复更新,对有待更新的顶点移入队列,已更新的顶点移出队列,避免待更新的顶点中存在重复顶点
SPFA算法 此处为SPFA算法详解 用dis数组记录源点到有向图上任意一点距离,其中源点到自身距离为0,到其他点距离为 INF。将源点入队,并重复以下步骤: 1、队首x出队 2、遍历所有以队首为起点的有向边(x,i),若...