题意：一个池塘中分布着n块可供青蛙跳跃的石头，坐标分别为sto[i].x和sto[i].y，给出Freddy和Fiona站的石头，问Freddy想借助这些石头，跳去Fiona那，它的跳跃距离至少是多少？
思路：dijkstra的变形。由于每条边的权值必为正，故开始时就对连接Freddy点(源点)的所有边进行松弛，得出最小dict[]值的点s，其值便已确定，以后不会再改变(这点很重要，证明)。然后以s为源点，继续这样的操作，直至Freddy这点的dict[]值被确定。最坏情况下，每条边都访问一次，时间复杂度为0(n^2)。
AC代码如下：
[cpp]
#include
#include
#include
#include
#include
using namespace std;
const int Max=205;
const int INF=0x3f3f3f3f;
struct{
int x,y;
}sto[Max];
int n;
float edge[Max][Max],dict[Max];
bool vis[Max];
void init_data()
{
memset(vis,false,sizeof(vis));
vis[0]=true;
for(int i=1;i
dict[i]=INF;
}
}
float find_edge(int u,int v)
{
float dx=sto[u].x-sto[v].x;
float dy=sto[u].y-sto[v].y;
return sqrt(dx*dx+dy*dy);
}
void dijkstra()
{
int now=0,cnt=n-1;
while(cnt--)
{
int k;
float min_dis=INF;
for(int i=1;i
if(!vis[i])
{
if(dict[i]>max(dict[now],edge[i][now]))//取路程中最长的值
{
dict[i]=max(dict[now],edge[i][now]);
}
if(min_dis>dict[i])
{
min_dis=dict[i];
k=i;
}
}
}
if(k==1)return;
now=k;
vis[k]=true;
}
}
int main()
{
int t=0;
while(cin>>n&&n!=0)
{
init_data();
for(int i=0;i
cin>>sto[i].x>>sto[i].y;
for(int j=i-1;j>=0;j--)
{
float val = find_edge(i,j);
edge[i][j]=edge[j][i]=val;
}
}
dijkstra();
printf("Scenario #%d\nFrog Distance = %.3f\n\n", ++t, dict[1]);
}
return 0;
}
#include
#include
#include
#include
#include
using namespace std;
const int Max=205;
const int INF=0x3f3f3f3f;
struct{
int x,y;
}sto[Max];
int n;
float edge[Max][Max],dict[Max];
bool vis[Max];
void init_data()
{
memset(vis,false,sizeof(vis));
vis[0]=true;
for(int i=1;i
dict[i]=INF;
}
}
float find_edge(int u,int v)
{
float dx=sto[u].x-sto[v].x;
float dy=sto[u].y-sto[v].y;
return sqrt(dx*dx+dy*dy);
}
void dijkstra()
{
int now=0,cnt=n-1;
while(cnt--)
{
int k;
float min_dis=INF;
for(int i=1;i
if(!vis[i])
{
if(dict[i]>max(dict[now],edge[i][now]))//取路程中最长的值
{
dict[i]=max(dict[now],edge[i][now]);
}
if(min_dis>dict[i])
{
min_dis=dict[i];
k=i;
}
}
}
if(k==1)return;
now=k;
vis[k]=true;
}
}
int main()
{
int t=0;
while(cin>>n&&n!=0)
{
init_data();
for(int i=0;i
cin>>sto[i].x>>sto[i].y;
for(int j=i-1;j>=0;j--)
{
float val = find_edge(i,j);
edge[i][j]=edge[j][i]=val;
}
}
dijkstra();
printf("Scenario #%d\nFrog Distance = %.3f\n\n", ++t, dict[1]);
}
return 0;
}