POJ2253 && ZOJ1942
POJ2253 && ZOJ1942
triplebee
发布于 2018-01-12 15:26:05
发布于 2018-01-12 15:26:05
两种写法
用floyd算法，求所有点之间的最大跳的最小值，最后输出a[0][1]，即起始与终止位置的最小值，采用传递闭包的思路，时间复杂度较高，但代码简单。
或者Dijkstru的变形，两点间的最短距离，只是最短距离的求法有变，当前加入一个点时，松弛方法不同，时间复杂度降低了。
在数据结构编程实验一书上，看到二分的写法，感觉很巧妙。也是把三种写法都看一下，前两种为找到的代码，最后一种是自己写的。
floyd
#include<stdio.h>
#include<math.h>
#define N 205
double a[N][N];
int n,x[N],y[N];
double dist(int i,int j)
{
return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
double max(double x,double y)
{
return x>y?x:y;
}
double min(double x,double y)
{
return x>y?y:x;
}
void floyd()
{
int i,j,k;
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j]=min(a[i][j],max(a[i][k],a[k][j]));
}
int main()
{
int i,j,num=1;
while(scanf("%d",&n),n!=0)
{
for(i=0;i<n;i++)
scanf("%d%d",&x[i],&y[i]);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j]=dist(i,j);
floyd();
printf("Scenario #%d/n",num);
printf("Frog Distance = %.3f/n/n",a[0][1]);
num++;
}
return 0;
} dij
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define N 205
#define MAX 100000000
double a[N][N],dis[N];
int n,x[N],y[N],s[N];
double dist(int i,int j)
{
return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
double max(double a,double b)
{
if(a>b)
return a;
return b;
}
double Dijkstru()
{
int i,j,u;
double minDis;
for(i=0;i<n;i++)
{
dis[i]=a[0][i];
s[i]=0;
}
s[0]=1;
for(i=1;i<n;i++)
{
minDis=MAX;
u=-1;
for(j=0;j<n;j++)
if(s[j]==0 && dis[j]<minDis)
{
u=j;
minDis=dis[j];
}
if(u==-1) break;
s[u]=1;
if(s[1]==1)
return dis[1];
for(j=0;j<n;j++)
if(s[j]==0 && max(dis[u],a[u][j])<dis[j])
dis[j]=max(dis[u],a[u][j]);
}
return dis[1];
}
int main()
{
int i,j,num=1;
double result;
while(scanf("%d",&n),n!=0)
{
for(i=0;i<n;i++)
scanf("%d%d",&x[i],&y[i]);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j]=dist(i,j);
result=Dijkstru();
printf("Scenario #%d/n",num);
printf("Frog Distance = %.3f/n/n",result);
num++;
}
return 0;
} 最巧妙的二分
枚举结果的方法不同于一般人做这题的思路，不过复杂度有点高。
875ms，全当开阔一下思维
#include<cstring>
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int n;
struct point
{
int x,y;
}p[210];
bool can[210][210];
int main()
{
int t=0;
int i,j,k;
while(cin>>n && n)
{
t++;
double map[210][210]={0};
for(i=0;i<n;i++)
cin>>p[i].x>>p[i].y;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
map[i][j]=map[j][i]=sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));
cout<<"Scenario #"<<t<<endl;
double up=100000,low=0,mid;
while((up-low)>=1e-5)
{
mid=(up+low)/2;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(map[i][j]>mid)
can[i][j]=false;
else
can[i][j]=true;
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
can[i][j]|=can[i][k]&can[k][j];
if(can[0][1])
up=mid;
else
low=mid;
}
printf("Frog Distance = %.3f\n\n",up);
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2014-03-30 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读