首页 > 代码库 > shortpath2253
shortpath2253
Freddy Frog暗恋Fiona Frog，在他们之间有n快石头，告诉你这n快石头的坐标，第一快为Freddy Frog的坐标，第n块为Finoa Frog的坐标，Freddy可以借助石头经过任何路径到达Fiona那里，问他最小的弹跳距离是多少
与1797一样，只不过这里求的是所有 路径里最大边 中最小的那个
因此第一步取最小的那个。后面如果有更大的边，则需要松弛，因为路径上有更大的边，因此需要更新该路径的最大边。
当然用FOLYD算法也可以 后面也有：
#include<stdio.h>
#include<string.h>
#include<math.h>
const int MAXN=300;
const int INF=0x7fffffff;
int map[MAXN][MAXN];
int dist[MAXN];
int n;
struct Point
{
int x,y;
}pnt[MAXN];
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a<b?a:b;
}
int _dist(Point a,Point b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
void Dijkstra()
{
int i,j,k;
int min;
int p[MAXN];
for (i=1;i<=n;i++)
{
p[i]=0;
dist[i]=map[1][i];//1是源点，具体的源点不同
}
dist[1]=0;
p[1]=1;
for (i=1;i<=n-1;i++)
{
min=INF;
k=0;
for (j=1;j<=n;j++)
{
if(!p[j] && dist[j]<min)
{
min=dist[j];
k=j;
}
}
if(k==0) return ;
p[k]=1;
for (j=1;j<=n;j++)
{
if(!p[j] && map[k][j]!=INF)
{
if(dist[j]>max(dist[k],map[k][j]))
dist[j]=max(dist[k],map[k][j]);
}
}
}
}
int main()
{
int cas=1,i,j;
while(scanf("%d",&n) && n)
{
for (i=1;i<=n;i++)
{
scanf("%d%d",&pnt[i].x,&pnt[i].y);
}
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{
if(i==j) map[i][j]=0;
else map[i][j]=INF;
}
for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
{
map[i][j]=_dist(pnt[i],pnt[j]);
}
}
Dijkstra();
printf("Scenario #%d\n",cas++);
printf("Frog Distance = %.3f\n\n",sqrt(1.0*dist[2]));//在计算距离时一直没有开方，因此这里需要开方
}
return 0;
}
当然用FOLYD算法也可以 后面也有：
//Memory Time
//584K 63MS
#include<iostream>
#include<math.h>
#include<iomanip>
using namespace std;
class coordinate
{
public:
double x,y;
}point[201];
double path[201][201]; //两点间的权值
int main(void)
{
int i,j,k;
int cases=1;
while(cases)
{
/*Read in*/
int n; //numbers of stones;
cin>>n;
if(!n)break;
for(i=1;i<=n;i++)
cin>>point[i].x>>point[i].y;
/*Compute the weights of any two points*/
for(i=1;i<=n-1;i++)
for(j=i+1;j<=n;j++)
{
double x2=point[i].x-point[j].x;
double y2=point[i].y-point[j].y;
path[i][j]=path[j][i]=sqrt(x2*x2+y2*y2); //双向性
}
/*Floyd Algorithm*/
for(k=1;k<=n;k++) //k点是第3点
for(i=1;i<=n-1;i++) //主要针对由i到j的松弛,最终任意两点间的权值都会被分别松弛为最大跳的最小（但每个两点的最小不一定相同）i到i不需要计算
for(j=i+1;j<=n;j++)
if(path[i][k]<path[i][j] && path[k][j]<path[i][j]) //当边ik,kj的权值都小于ij时，则走i->k->j路线，否则走i->j路线
if(path[i][k]<path[k][j]) //当走i->k->j路线时，选择max{ik,kj},只有选择最大跳才能保证连通
path[i][j]=path[j][i]=path[k][j];
else
path[i][j]=path[j][i]=path[i][k];
cout<<"Scenario #"<<cases++<<endl;
cout<<fixed<<setprecision(3)<<"Frog Distance = "<<path[1][2]<<endl;
//fixed用固定的小数点位数来显示浮点数（包括小数位全为0)
//setprecision(3)设置小数位数为3
cout<<endl;
}
return 0;
}