題意：一個池塘中分布著n塊可供青蛙跳躍的石頭，坐標分別為sto[i].x和sto[i].y，給出Freddy和Fiona站的石頭，問Freddy想借助這些石頭，跳去Fiona那，它的跳躍距離至少是多少？
思路：dijkstra的變形。由於每條邊的權值必為正，故開始時就對連接Freddy點(源點)的所有邊進行松弛，得出最小dict[]值的點s，其值便已確定，以後不會再改變(這點很重要，證明)。然後以s為源點，繼續這樣的操作，直至Freddy這點的dict[]值被確定。最壞情況下，每條邊都訪問一次，時間復雜度為0(n^2)。
AC代碼如下：
[cpp]
#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
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<n;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<n;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<n;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 <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
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<n;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<n;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<n;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;
}
